Sachverhalt:
A.
Das Bezirksgericht Affoltern verurteilte A._ am 24. November 2014 wegen qualifizierter Vergewaltigung, mehrfacher qualifizierter sexueller Nötigung sowie Widerhandlung gegen das Ausländergesetz zu einer Freiheitsstrafe von neun Jahren und ordnete die Verwahrung an. Das Obergericht des Kantons Zürich stellte am 18. Oktober 2016 fest, das Urteil des Bezirksgerichts sei im Schuldpunkt in Rechtskraft erwachsen. Es bestrafte A._ mit einer Freiheitsstrafe von 81⁄2 Jahren und sah von der Anordnung einer Verwahrung sowie einer therapeutischen Massnahme ab. Eine von der Oberstaatsanwaltschaft des Kantons Zürich dagegen erhobene Beschwerde hiess das Bundesgericht teilweise gut und wies die Sache zur neuen Beurteilung an das Obergericht zurück. Zur Begründung führte es aus, es sei nicht zu beanstanden, dass der psychiatrische Sachverständige in seinem Gutachten vom 12. Juli 2012 (ergänzt am 25. Juli 2013) die aus dem Strafregister entfernte Vorstrafe aus dem Jahr 2000 wegen vorsätzlicher Tötung, Raub und Diebstahl bei der Realprognose berücksichtigt habe. Für die Strafbehörden gelte jedoch insofern ein Verwertungsverbot. Deshalb müsste aus dem Gutachten hervorgehen, inwiefern diese im Jahr 1999 begangenen Delikte mit den noch im Strafregister aufgeführten Delikten (Verurteilung vom 23. März 2006 wegen mehrfach versuchtem Raub, Sachbeschädigung und Übertretung des Betäubungsmittelgesetzes) und den zu beurteilenden Delikten im Zusammenhang stünden und wie stark sie sich noch realprognostisch auswirkten. Diese Differenzierung habe der Sachverständige soweit ersichtlich nicht vorgenommen. Indem die Vorinstanz das psychiatrische Gutachten selbständig analysiert habe und zum Schluss gelangt sei, der Raub und die Raubversuche hätten im Vergleich zum Tötungsdelikt klarerweise eine stark untergeordnete Bedeutung, weshalb es sich nicht rechtfertige, gestützt darauf die Verwahrung anzuordnen, masse sie sich psychiatrische Fachkenntnisse an und verletze Bundesrecht (Urteil 6B_281/2017 vom 16. Oktober 2017).
Das Obergericht beauftragte daraufhin einen neuen Sachverständigen. Gestützt auf dessen Gutachten vom 16. Oktober 2018 (ergänzt am 13. Januar 2020) ordnete es mit Urteil vom 27. April 2020 die Verwahrung an. Zur Begründung hielt es fest, gemäss dem Gutachten lasse sich die Frage, wie stark sich aus dem Strafregister gelöschte Straftaten realprognostisch auswirkten, nicht beantworten. Bei einer ganzheitlichen Betrachtung bestehe eine hohe (deutliche) Gefahr der Begehung weiterer Straftaten wie Raub, Körperverletzung und Sexualstraftaten. Weil eine therapeutische Massnahme nach <ref-law> keinen Erfolg verspreche, seien die Voraussetzungen für eine Verwahrung nach <ref-law> erfüllt. Auf die Beschwerde von A._ hin hob das Bundesgericht dieses Urteil ebenfalls auf und wies die Sache zur neuen Entscheidung an das Obergericht zurück. In Verletzung des rechtlichen Gehörs habe das Obergericht nicht dargelegt, weshalb es einzig auf das aktuelle Gutachten abstelle und weshalb es die Verwahrung als verhältnismässig erachte. Zudem hätte es zur Frage, ob es unmöglich sei zu sagen, wie stark sich die aus dem Strafregister entfernten Vorstrafen noch realprognostisch auswirkten, die Meinung eines weiteren Sachverständigen einholen müssen (Urteil 6B_770/2020 vom 25. November 2020).
Da am 23. Mai 2020 das ordentliche Ende der Freiheitsstrafe von 81⁄2 Jahren erreicht war, hatte das Obergericht A._ mit Präsidialverfügung vom 18. Mai 2020 wegen Flucht- und Wiederholungsgefahr zur Sicherstellung des Vollzugs der Verwahrung in Sicherheitshaft versetzt. Zudem gab es gestützt auf den zweiten bundesgerichtlichen Rückweisungsentscheid eine weitere psychiatrische Begutachtung in Auftrag. Mit Urteil vom 20. September 2021 sah es sowohl von einer therapeutischen Massnahme als auch einer Verwahrung ab. Mit Präsidialverfügung vom gleichen Tag ordnete es an, A._ werde per sofort aus der Sicherheitshaft entlassen und dem Migrationsamt des Kantons Zürich zugeführt.
B.
Mit Beschwerde in Strafsachen vom 23. September 2021 beantragt die Oberstaatsanwaltschaft, die Präsidialverfügung vom 20. September 2021 sei aufzuheben und es sei bis zum Vorliegen eines begründeten und rechtskräftigen Entscheids über die Anordnung einer Verwahrung nach <ref-law> die Sicherheitshaft anzuordnen. Eventualiter sei die Sache an die Vorinstanz zur unverzüglichen Anordnung der Sicherheitshaft zurückzuweisen. Der Entscheid sei auch dem Migrationsamt mitzuteilen. Als vorsorgliche Massnahme sei A._ zudem für die Dauer des bundesgerichtlichen Verfahrens zu inhaftieren. Auch der Entscheid darüber sei dem Migrationsamt mitzuteilen.
Mit Verfügung vom 28. September 2021 lud das Bundesgericht den Beschwerdegegner und das Obergericht zur Vernehmlassung ein und ordnete gleichzeitig an, bis zum Entscheid über das Gesuch um vorsorgliche Massnahmen hätten alle Vollziehungsvorkehrungen zu unterbleiben bzw. sei die Sicherheitshaft aufrechtzuerhalten.
Der Beschwerdegegner beantragt, die Beschwerde und der Antrag auf vorsorgliche Massnahmen seien abzuweisen. Das Obergericht verzichtete auf eine Stellungnahme. Zudem stellte es dem Bundesgericht eine Präsidialverfügung vom 29. September 2021 zu, mit der es den Beschwerdegegner in Sicherheitshaft versetzte. In dieser Verfügung wird ausgeführt, der Beschwerdegegner sei am 20. September 2021 aus der Sicherheitshaft entlassen und dem Migrationsamt zugeführt worden. Gemäss Auskunft des Migrationsamts sei er mittlerweile in Ausschaffungshaft versetzt worden. In Nachachtung der Anweisung des Bundesgerichts sei er somit erneut in Untersuchungshaft zu versetzen.

Erwägungen:
1.
Die Eintretensvoraussetzungen sind erfüllt und geben zu keinen Bemerkungen Anlass (vgl. Urteil 1B_548/2017 vom 29. Januar 2018 E. 1).
2.
Gemäss <ref-law> müssen Entscheide, die der Beschwerde an das Bundesgericht unterliegen, die massgebenden Gründe tatsächlicher und rechtlicher Art, insbesondere die Angabe der angewendeten Gesetzesbestimmungen, enthalten. Aus dem Entscheid muss klar hervorgehen, von welchem festgestellten Sachverhalt die Vorinstanz ausgegangen ist und welche rechtlichen Überlegungen sie angestellt hat. Genügt ein Entscheid den Anforderungen gemäss <ref-law> nicht, so kann das Bundesgericht ihn in Anwendung von <ref-law> an die kantonale Behörde zur Verbesserung zurückweisen oder aufheben. Hingegen steht es ihm nicht zu, sich an die Stelle der Vorinstanz zu setzen, die ihrer Aufgabe nicht nachgekommen ist (zum Ganzen: <ref-ruling> E. 1.2.1; Urteil 1B_274/2021 vom 24. August 2021 E. 1; je mit Hinweisen).
Für die Anordnung von Sicherheitshaft nach Verbüssen der Freiheitsstrafe bedarf es insbesondere der hinreichenden Wahrscheinlichkeit, dass eine Massnahme angeordnet wird, welche die Sicherstellung des Beschwerdegegners erfordert (vgl. <ref-ruling> E. 2.3.1 und Urteil 1B_548/2017 vom 29. Januar 2018 E. 3.2 bezüglich der Sicherheitshaft im Nachverfahren betreffend die nachträgliche Verwahrung). Das Obergericht hat im angefochtenen Entscheid mit keinem Wort begründet, weshalb es mit dem am gleichen Tag ergangenen Urteil von der Anordnung von therapeutischen Massnahmen und einer Verwahrung absah. Jenes Urteil liegt zudem erst im Dispositiv vor und wurde auch nicht mündlich eröffnet. Daraus ergeben sich somit ebenfalls keine Hinweise auf die für den Haftentscheid massgebenden Gründe tatsächlicher und rechtlicher Art.
3.
Der angefochtene Entscheid ist in Anwendung von <ref-law> aufzuheben und die Sache an das Obergericht des Kantons Zürich zurückzuweisen, damit dieses einen Entscheid trifft, der den Anforderungen von <ref-law> genügt. Dabei wird es das Beschleunigungsgebot in Haftsachen zu beachten haben (<ref-law>, <ref-law>). Das Gesuch der Beschwerdeführerin um vorsorgliche Massnahmen wird damit gegenstandslos.
Der unterliegende Beschwerdegegner stellt ein Gesuch um unentgeltliche Rechtspflege. Da die gesetzlichen Voraussetzungen erfüllt sind, ist das Gesuch gutzuheissen (<ref-law>).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird gutgeheissen, der angefochtene Entscheid aufgehoben und die Sache zu neuem Entscheid an das Obergericht zurückgewiesen.
2.
Das Gesuch des Beschwerdegegners um unentgeltliche Rechtspflege wird gutgeheissen.
2.1. Es werden keine Gerichtskosten erhoben.
2.2. Rechtsanwalt Vijay Singh wird zum unentgeltlichen Rechtsbeistand ernannt und für das bundesgerichtliche Verfahren aus der Bundesgerichtskasse mit Fr. 1'500.-- entschädigt.
3.
Dieses Urteil wird den Parteien, dem Obergericht des Kantons Zürich, II. Strafkammer, und dem Migrationsamt des Kantons Zürich schriftlich mitgeteilt.
Lausanne, 18. Oktober 2021
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Kneubühler
Der Gerichtsschreiber: Dold