Sachverhalt:
A.
X._ wurde am 18. März 2004 wegen Vergewaltigung und sexueller Nötigung zu einer Zuchthausstrafe von 4 Jahren verurteilt. Der Vollzug der Strafe wurde zugunsten einer Verwahrung aufgeschoben.
B.
Im Rahmen der jährlichen Überprüfung lehnte das Amt für Justizvollzug des Kantons Zürich am 26. August 2015 die bedingte Entlassung von X._ ab. Gegen die Verfügung des Amtes für Justizvollzug erhob X._ Rekurs bei der Direktion der Justiz und des Inneren des Kantons Zürich, welche das Rechtsmittel am 24. November 2015 abwies. Die gegen diesen Entscheid erhobene Beschwerde wies das Verwaltungsgericht des Kantons Zürich am 13. September 2016 ab.
C.
X._ führt Beschwerde in Strafsachen. Er beantragt, das Urteil des Verwaltungsgerichts sei aufzuheben und die Sache zu neuer Entscheidung an dieses zurückzuweisen. Für die Prüfung der bedingten Entlassung im vorinstanzlichen Verfahren sei ein aktuelles und unabhängiges medizinisches Gutachten einzuholen. Eventualiter sei die Entlassung wegen Verletzung des Abstandsgebotes anzuordnen. X._ ersucht um unentgeltliche Rechtspflege und Verbeiständung. Das Amt für Justizvollzug und das Verwaltungsgericht beantragen, die Beschwerde sei abzuweisen. X._ replizierte.

Erwägungen:
1.
1.1. Der Beschwerdeführer rügt, die Vorinstanz stütze ihren Entscheid auf ein nicht aktuelles Gutachten. Er macht zusammengefasst geltend, dass weder sein physischer Gesundheitszustand, welcher sich seit 2010 und insbesondere seit 2014 erheblich verschlechtert habe, noch sein Alter als deliktsprotektiver Faktor Gegenstand einer gutachterlichen Auseinandersetzung gewesen seien.
1.2. Die Vorinstanz erwägt diesbezüglich, dass für die Gefahr eines Rückfalls in erster Linie die sexuelle und kombinierte Persönlichkeitsstörung des Beschwerdeführers massgebend sei. Die Frage, inwieweit er körperlich oder altersmässig noch in der Lage sei, ein Sexualdelikt zu begehen, betreffe dagegen die technische Ausführung, nachdem ein Tatentschluss bereits gefasst worden sei, und sei daher für die Frage eines Rückfalls von untergeordneter Bedeutung. Die Erwartung von <ref-law> werde eben nicht erfüllt, wenn die Begehung einzig deswegen nicht erfolgen könne, weil der körperliche Zustand des Täters dies nicht mehr erlaube. Überdies wäre es für den Beschwerdeführer in Freiheit auch ohne Anwendung physischer Gewalt einfach, eine Prostituierte in seine Wohnung zu bestellen und zu bedrohen.
1.3.
1.3.1. Nach <ref-law> wird der Täter aus der Verwahrung bedingt entlassen, sobald zu erwarten ist, dass er sich in der Freiheit bewährt. Die in dieser Bestimmung vorausgesetzte Erwartung der Bewährung bezieht sich auf Straftaten im Sinne von <ref-law>. Es muss mithin die ernsthafte Gefahr bestehen, dass der Verwahrte in Freiheit weitere schwere Gewalt- und Sexualstraftaten begehen könnte, welche geeignet sind, die physische, psychische oder sexuelle Integrität der Opfer schwer zu beeinträchtigen. Dass sich der Verwahrte in Freiheit anderweitig strafbar machen könnte, steht einer bedingten Entlassung nicht entgegen (<ref-ruling> E. 2.1.1; <ref-ruling> E. 1.1.2.2; je mit Hinweisen).
Gemäss <ref-law> prüft die zuständige Behörde, auf Gesuch hin oder von Amtes wegen: (lit. a) mindestens einmal jährlich, und erstmals nach Ablauf von zwei Jahren, ob und wann der Täter aus der Verwahrung bedingt entlassen werden kann; (lit. b) mindestens alle zwei Jahre, und erstmals vor Antritt der Verwahrung, ob die Voraussetzungen für eine stationäre therapeutische Behandlung gegeben sind und beim zuständigen Gericht entsprechend Antrag gestellt werden soll (<ref-law>). Sie trifft ihren Entscheid nach Abs. 1 gestützt auf: (lit. a) einen Bericht der Anstaltsleitung; (lit. b) eine unabhängige sachverständige Begutachtung im Sinne von <ref-law>; (lit. c) die Anhörung einer Kommission nach Art. 62d Abs. 2; (lit. d) die Anhörung des Täters (<ref-law>). Der Sachverständige hat im (Prognose-) Gutachten namentlich zum aktuellen Gesundheitszustand des Exploranden, zu seinen Verhaltensweisen, zum bisherigen Vollzugsverlauf sowie zur Rückfallgefahr und zur Legalprognose Stellung zu nehmen (Urteil 6B_1050/2013 vom 8. September 2014 E. 4.2.).
Zur Beantwortung der Frage, ob ein früheres Gutachten hinreichend aktuell ist, ist nicht primär auf das formelle Kriterium des Alters des Gutachtens abzustellen. Massgeblich ist vielmehr die materielle Frage, ob Gewähr dafür besteht, dass sich die Ausgangslage seit der Erstellung des Gutachtens nicht gewandelt hat. Soweit ein früheres Gutachten mit Ablauf der Zeit und zufolge veränderter Verhältnisse an Aktualität eingebüsst hat, sind neue Abklärungen unabdingbar (<ref-ruling> E. 4.3; Urteile 6B_56/2015 vom 27. November 2015 E. 4.3.1; 6B_1230/2014 vom 20. April 2015 E. 2.3.2; je mit Hinweisen).
1.3.2. <ref-law> bestimmt lediglich, dass der Täter bedingt zu entlassen ist, sobald zu erwarten ist, dass er sich in Freiheit bewährt. Entgegen der Auffassung der Vorinstanz besteht eine ernsthafte Gefahr weiterer schwerer Gewalt- und Sexualstraftaten nicht, wenn der Täter aufgrund körperlicher Einschränkungen oder seines Alters dazu nicht mehr in der Lage ist. Der Täter wäre auch in einem solchen Fall bedingt zu entlassen. Der Beschwerdeführer wurde alleine im Jahre 2015 drei Mal hospitalisiert, wobei er auch operiert werden musste (vgl. Urteil, S. 18). Diesem Umstand können das Gutachten vom 26. April 2010 (Akten Vorinstanz, act. 11.2/110) und das Ergänzungsgutachten vom 13. Oktober 2014 (Akten Vorinstanz, act. 11.3/227) selbstredend nicht Rechnung tragen. Zur Frage, ob und wie sich der aktuelle (körperliche) Gesundheitszustand des Beschwerdeführers auf die Gefahr neuer Straftaten auswirkt, besteht mithin keine gutachterliche Abklärung. Ebenso wenig äussert sich der Gutachter zu der vom Beschwerdeführer geltend gemachten protektiven Wirkung des fortgeschrittenen Alters (vgl. hierzu Urteil 6B_424/2015 vom 4. Dezember 2015 E. 3.7).
Die Sache ist bereits aus diesen Gründen an die Vorinstanz zurückzuweisen, damit diese ein unabhängiges, aktuelles und umfassendes Gutachten zu den gesundheitlichen Beschwerden und dessen Auswirkung auf die Gefahr neuer Straftaten einholt. Es erübrigt sich somit, auf die weiteren Vorbringen des Beschwerdeführers einzugehen.
2.
Die Beschwerde ist gutzuheissen. Die Sache ist zu neuer Entscheidung an die Vorinstanz zurückzuweisen. Für das bundesgerichtliche Verfahren sind keine Kosten zu erheben (Art. 66 Abs. 1 und 4 BGG). Der Beschwerdeführer hat Anspruch auf eine angemessene Parteientschädigung (<ref-law>). Diese ist praxisgemäss dem Rechtsvertreter auszurichten. Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung wird gegenstandslos.

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird gutgeheissen. Das Urteil des Verwaltungsgerichts des Kantons Zürich vom 13. September 2016 wird aufgehoben und die Sache zu neuer Entscheidung an die Vorinstanz zurückgewiesen.
2.
Es werden keine Kosten erhoben.
3.
Der Kanton Zürich hat dem Rechtsvertreter des Beschwerdeführers, Rechtsanwalt Dr. Andres Büsser, eine Parteientschädigung von Fr. 3'000.-- zu bezahlen.
4.
Dieses Urteil wird den Parteien und dem Verwaltungsgericht des Kantons Zürich, 3. Abteilung, Einzelrichter, schriftlich mitgeteilt.
Lausanne, 29. Juni 2017
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Denys
Der Gerichtsschreiber: Moses