1Universiteit van Birmingham
2Universiteit van Oxford
3ILLC, Universiteit van Amsterdam (tot 2020)
4Radboud Universiteit Nijmegen
Vind je dit artikel interessant of wil je het bespreken? Scite of laat een reactie achter op SciRate.
Abstract
Vertalingen tussen het kwantumcircuitmodel en het op metingen gebaseerde eenrichtingsmodel zijn nuttig voor verificatie en optimalisatie van kwantumberekeningen. Ze maken cruciaal gebruik van een eigenschap die bekend staat als gflow. Terwijl gflow is gedefinieerd voor eenrichtingsberekeningen die metingen in drie verschillende vlakken van de Bloch-bol mogelijk maken, heeft het meeste onderzoek zich tot nu toe gericht op berekeningen die alleen metingen in het XY-vlak bevatten. Hier geven we het eerste circuit-extractie-algoritme dat werkt voor eenrichtingsberekeningen met metingen in alle drie de vlakken en met gflow. Het algoritme is efficiënt en de resulterende circuits bevatten geen ancillae. Eenrichtingsberekeningen worden weergegeven met behulp van de ZX-calculus, daarom vertegenwoordigt het algoritme ook de meest algemeen bekende procedure voor het extraheren van schakelingen uit ZX-diagrammen. Bij het ontwikkelen van dit algoritme generaliseren we verschillende concepten en resultaten die voorheen bekend waren voor berekeningen die alleen XY-vlakmetingen bevatten. We brengen verschillende bekende herschrijfregels voor meetpatronen samen en formaliseren ze in een uniforme notatie met behulp van de ZX-calculus. Deze regels worden gebruikt om meetpatronen te vereenvoudigen door het aantal qubits te verminderen met behoud van zowel de semantiek als het bestaan van gflow. De resultaten kunnen worden toegepast op circuitoptimalisatie door circuits te vertalen naar patronen en weer terug.
Populaire samenvatting
Vertalingen tussen deze twee modellen zijn nuttig voor optimalisatie (bv. Benodigde tijd of aantal gebruikte poorten) en voor verificatie (dwz bevestigen dat de berekening inderdaad de gewenste procedure uitvoert). Hoewel het gemakkelijk is om van circuits naar op metingen gebaseerde berekeningen te vertalen, werkten eerdere algoritmen voor het vertalen van op metingen gebaseerde berekeningen naar circuits niet in alle gevallen.
In dit werk geven we het eerste vertaalalgoritme dat werkt voor alle op metingen gebaseerde berekeningen met een eigenschap genaamd extended gflow, die alle berekeningen omvat die gewoonlijk worden bestudeerd. Vervolgens gebruiken we het algoritme om kwantumcircuits te optimaliseren door ze te vertalen naar het op metingen gebaseerde model en terug. De vertalingen worden uitgevoerd met behulp van de ZX-calculus, een grafische taal die zowel kwantumcircuits als op metingen gebaseerde berekeningen kan uitdrukken.
► BibTeX-gegevens
► Referenties
[1] Scott Aaronson en Daniel Gottesman. Verbeterde simulatie van stabilisatorcircuits. Fysieke beoordeling A, 70 (5): 052328, 2004. 10.1103 / PhysRevA.70.052328.
https: / / doi.org/ 10.1103 / PhysRevA.70.052328
[2] Matthew Amy, Dmitri Maslov, Michele Mosca en Martin Roetteler. Een meet-in-the-middle-algoritme voor snelle synthese van diepte-optimale kwantumcircuits. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 32 (6): 818-830, 2013. 10.1109 / TCAD.2013.2244643.
https: / / doi.org/ 10.1109 / TCAD.2013.2244643
[3] Matthew Amy, Dmitri Maslov en Michele Mosca. Polynoom-tijd T-diepte optimalisatie van Clifford + T-circuits via matroid-partitionering. IEEE-transacties in computerondersteund ontwerp van geïntegreerde schakelingen en systemen, 33 (10): 1476–1489, 2014. 10.1109 / TCAD.2014.2341953.
https: / / doi.org/ 10.1109 / TCAD.2014.2341953
[4] Miriam Backens. De ZX-calculus is compleet voor de kwantummechanica van de stabilisator. New Journal of Physics, 16 (9): 093021, 2014. ISSN 1367-2630. 10.1088 / 1367-2630 / 16/9/093021.
https://doi.org/10.1088/1367-2630/16/9/093021
[5] Miriam Backens. De stabilisator ZX-calculus compleet maken voor scalairen. In Chris Heunen, Peter Selinger en Jamie Vicary, redacteurs, Proceedings of the 12th International Workshop on Quantum Physics and Logic (QPL 2015), volume 195 of Electronic Proceedings in Theoretical Computer Science, pagina's 17–32, 2015. 10.4204 / EPTCS .195.2.
https: / / doi.org/ 10.4204 / EPTCS.195.2
[6] Gregory Bard. Het bereiken van een log (n) versnelling voor booleaanse matrixbewerkingen en het berekenen van de complexiteit van de dichte lineaire algebra-stap van algebraïsche stroomciper-aanvallen en van integer-factorisatiemethoden. IACR Cryptology ePrint Archive, 2006: 163, 01 2006.
[7] Xiaoning Bian en Peter Selinger. Relaties voor 2-qubit Clifford + T-operatorgroep, 2015. URL https: / / mathstat.dal.ca/ xbian / talks / slide_cliffordt2.pdf.
https: / / mathstat.dal.ca/ ~ xbian / talks / slide_cliffordt2.pdf
[8] Anne Broadbent en Elham Kashefi. Parallel maken van kwantumcircuits. Theoretische informatica, 410 (26): 2489-2510, 2009. 10.1016 / j.tcs.2008.12.046.
https: / / doi.org/ 10.1016 / j.tcs.2008.12.046
[9] Daniel E Browne, Elham Kashefi, Mehdi Mhalla en Simon Perdrix. Gegeneraliseerde stroming en determinisme in op metingen gebaseerde kwantumberekeningen. New Journal of Physics, 9 (8): 250, 2007. 10.1088 / 1367-2630 / 9/8/250.
https://doi.org/10.1088/1367-2630/9/8/250
[10] Daniel E. Browne, Elham Kashefi en Simon Perdrix. Computationele diepte-complexiteit van op metingen gebaseerde kwantumberekeningen. In Theory of Quantum Computation, Communication, and Cryptography (TQC'10), volume 6519, pagina's 35-46. LNCS, 2011. 10.1007 / 978-3-642-18073-6_4.
https://doi.org/10.1007/978-3-642-18073-6_4
[11] B. Coecke en R. Duncan. Interactie met kwantumwaarnemingen: categorische algebra en diagrammatica. New Journal of Physics, 13: 043016, 2011. 10.1088 / 1367-2630 / 13/4/043016. arXiv: quant-ph / 09064725.
https://doi.org/10.1088/1367-2630/13/4/043016
arXiv: quant-ph / 09064725
[12] Bob Coecke en Aleks Kissinger. Kwantumprocessen in beeld brengen: een eerste cursus in kwantumtheorie en schematisch redeneren. Cambridge University Press, 2017. ISBN 9781107104228 / 10.1017.
https: / / doi.org/ 10.1017 / 9781316219317
[13] Alexander Cowtan, Silas Dilkes, Ross Duncan, Will Simmons en Seyon Sivarajah. Fasegadgetsynthese voor ondiepe circuits. In Bob Coecke en Matthew Leifer, redacteuren, Proceedings 16th International Conference on Quantum Physics and Logic, Chapman University, Orange, CA, VS, 10-14 juni 2019, volume 318 van Electronic Proceedings in Theoretische Computerwetenschappen, pagina's 213-228. Open Publishing Association, 2020a. 10.4204 / EPTCS.318.13.
https: / / doi.org/ 10.4204 / EPTCS.318.13
[14] Alexander Cowtan, Will Simmons en Ross Duncan. Een generieke compilatiestrategie voor de unitaire gekoppelde cluster Ansatz. arXiv-voordruk arXiv: 2007.10515, 2020b.
arXiv: 2007.10515
[15] Raphael Dias da Silva en Ernesto F Galvão. Compacte kwantumcircuits van eenzijdige kwantumberekening. Physical Review A, 88 (1): 012319, 2013. 10.1103 / physreva.88.012319.
https: / / doi.org/ 10.1103 / physreva.88.012319
[16] Raphael Dias da Silva, Einar Pius en Elham Kashefi. Globale optimalisatie van kwantumcircuits. arXiv: 1301.0351, 2013.
arXiv: 1301.0351
[17] V. Danos en E. Kashefi. Determinisme in het eenrichtingsmodel. Phys. Rev. A, 74 (052310), 2006. 10.1103 / PhysRevA.74.052310.
https: / / doi.org/ 10.1103 / PhysRevA.74.052310
[18] Vincent Danos, Elham Kashefi en Prakash Panangaden. De meetrekening. J. ACM, 54 (2), april 2007. 10.1145 / 1219092.1219096.
https: / / doi.org/ 10.1145 / 1219092.1219096
[19] Vincent Danos, Elham Kashefi, Prakash Panangaden en Simon Perdrix. Uitgebreide meetcalculus, pagina's 235-310. Cambridge University Press, 2009. 10.1017 / CBO9781139193313.008.
https: / / doi.org/ 10.1017 / CBO9781139193313.008
[20] Niel de Beaudrap. Semantiek van een unitair circuit voor op metingen gebaseerde berekeningen. International Journal of Quantum Information, 8 (01n02): 1–91, 2010. 10.1142 / s0219749910006113.
https: / / doi.org/ 10.1142 / s0219749910006113
[21] Niel de Beaudrap, Xiaoning Bian en Quanlong Wang. Technieken om $ pi / 4 $ -pariteitsfasecircuits te verminderen, gemotiveerd door de ZX-calculus. In Bob Coecke en Matthew Leifer, redacteuren, Proceedings 16th International Conference on Quantum Physics and Logic, Chapman University, Orange, CA, VS, 10-14 juni 2019, volume 318 van Electronic Proceedings in Theoretische Computerwetenschappen, pagina's 131-149. Open Publishing Association, 2020 / EPTCS.10.4204.
https: / / doi.org/ 10.4204 / EPTCS.318.9
[22] Olivia Di Matteo en Michele Mosca. Parallelle kwantumcircuitsynthese. Quantum Science and Technology, 1 (1): 015003, 2016. 10.1088 / 2058-9565 / 1/1/015003.
https://doi.org/10.1088/2058-9565/1/1/015003
[23] Ross Duncan en Simon Perdrix. Grafiek stelt en de noodzaak van Euler-ontbinding. Wiskundige theorie en computerpraktijk, pagina's 167-177, 2009. 10.1007 / 978-3-642-03073-4_18.
https://doi.org/10.1007/978-3-642-03073-4_18
[24] Ross Duncan en Simon Perdrix. Op metingen gebaseerde kwantumberekeningen herschrijven met gegeneraliseerde stroom. In Internationaal colloquium over automaten, talen en programmeren, pagina's 285-296. Springer, 2010. 10.1007 / 978-3-642-14162-1_24.
https://doi.org/10.1007/978-3-642-14162-1_24
[25] Ross Duncan en Simon Perdrix. Pivoteren maakt de ZX-calculus compleet voor echte stabilisatoren. In Bob Coecke en Matty Hoban, redacteuren, Proceedings of the 10th International Workshop on Quantum Physics and Logic (QPL), volume 171 van Electronic Proceedings in Theoretic Computer Science, pagina's 50-62. Open Publishing Association, 2014. 10.4204 / EPTCS.171.5.
https: / / doi.org/ 10.4204 / EPTCS.171.5
[26] Ross Duncan, Aleks Kissinger, Simon Perdrix en John van de Wetering. Grafentheoretische vereenvoudiging van kwantumcircuits met de ZX-calculus. Quantum, 4: 279, 6 2020. ISSN 2521-327X. 10.22331 / q-2020-06-04-279.
https://doi.org/10.22331/q-2020-06-04-279
[27] Maryam Eslamy, Mahboobeh Houshmand, Morteza Saheb Zamani en Mehdi Sedighi. Optimalisatie van meetpatronen voor kwantumberekeningen in één richting. International Journal of Theorhetic Physics, 57 (11): 3296–3317, 2018. 10.1007 / s10773-018-3844-x.
https: / / doi.org/ 10.1007 / s10773-018-3844-x
[28] Amar Hadzihasanovic, Kang Feng Ng en Quanlong Wang. Twee complete axiomatisaties van Pure-state Qubit Quantum Computing. In Proceedings of the 33rd Annual ACM / IEEE Symposium on Logic in Computer Science, LICS '18, pagina's 502-511, New York, NY, VS, 2018. ACM. ISBN 978-1-4503-5583-4. 10.1145 / 3209108.3209128.
https: / / doi.org/ 10.1145 / 3209108.3209128
[29] Nidhal Hamrit en Simon Perdrix. Omkeerbaarheid bij uitgebreide kwantumberekeningen op basis van metingen. In Jean Krivine en Jean-Bernard Stefani, redacteuren, Reversible Computation, pagina's 129–138. Springer International Publishing, 2015. ISBN 978-3-319-20860-2. 10.1007 / 978-3-319-20860-2_8.
https://doi.org/10.1007/978-3-319-20860-2_8
[30] M. Hein, J. Eisert en HJ Briegel. Verstrengeling van meerdere partijen in grafiektoestanden. Physical Review A, 69 (6): 062311, 2004. 10.1103 / PhysRevA.69.062311.
https: / / doi.org/ 10.1103 / PhysRevA.69.062311
[31] Marc Hein, Wolfgang Dür, Jens Eisert, Robert Raussendorf, M Nest en HJ Briegel. Verstrengeling in grafiektoestanden en zijn toepassingen. In G. Casati, DL Shepelyansky, P. Zoller en G. Benenti, redacteuren, Quantum Computers, Algorithms and Chaos, deel 162 van Proceedings of the International School of Physics "Enrico Fermi", pagina's 115-218. IOS Press Books, 2006. 10.3254 / 978-1-61499-018-5-115.
https://doi.org/10.3254/978-1-61499-018-5-115
[32] Mahboobeh Houshmand, Mehdi Sedighi, Morteza Saheb Zamani en Kourosh Marjoei. Targeting op kwantumcircuitsynthese om de kostenstatistieken van eenrichtingspatroon voor kwantumberekeningen te verbeteren. ACM Journal on Emerging Technologies in Computing Systems (JETC), 13 (4): 55, 2017. 10.1145 / 3064834.
https: / / doi.org/ 10.1145 / 3064834
[33] Monireh Houshmand, Mahboobeh Houshmand en Joseph F Fitzsimons. Minimale qubit-resources voor de realisatie van op metingen gebaseerde kwantumberekeningen. Physical Review A, 98 (1): 012318, 2018. 10.1103 / physreva.98.012318.
https: / / doi.org/ 10.1103 / physreva.98.012318
[34] Emmanuel Jeandel, Simon Perdrix en Renaud Vilmart. Schematisch redeneren voorbij Clifford + T-kwantummechanica. In Proceedings of the 33rd Annual ACM / IEEE Symposium on Logic in Computer Science, LICS '18, pagina's 569-578, New York, NY, VS, 2018a. ACM. 10.1145 / 3209108.3209139.
https: / / doi.org/ 10.1145 / 3209108.3209139
[35] Emmanuel Jeandel, Simon Perdrix en Renaud Vilmart. Een complete axiomatisering van de ZX-calculus voor Clifford + T Quantum Mechanics. In Proceedings of the 33rd Annual ACM / IEEE Symposium on Logic in Computer Science, LICS '18, pagina's 559-568, New York, NY, VS, 2018b. ACM. 10.1145 / 3209108.3209131.
https: / / doi.org/ 10.1145 / 3209108.3209131
[36] Aleks Kissinger en Arianne Meijer-van de Griend. CNOT-circuitextractie voor topologisch beperkte kwantumgeheugens. Quantum Information and Computation, 20: 581-596, 2020. 10.26421 / QIC20.7-8.
https: / / doi.org/ 10.26421 / QIC20.7-8
[37] Aleks Kissinger en John van de Wetering. Universele MBQC met gegeneraliseerde pariteitsfase-interacties en Pauli-metingen. Quantum, 3: 134, 2019 / q-10.22331-2019-04-26.
https://doi.org/10.22331/q-2019-04-26-134
[38] Aleks Kissinger en John van de Wetering. PyZX: grootschalige geautomatiseerde diagrammatische redenering. In Bob Coecke en Matthew Leifer, redacteuren, Proceedings 16th International Conference on Quantum Physics and Logic, Chapman University, Orange, CA, VS, 10-14 juni 2019, volume 318 van Electronic Proceedings in Theoretische Computerwetenschappen, pagina's 229-241. Open Publishing Association, 2020a. 10.4204 / EPTCS.318.14.
https: / / doi.org/ 10.4204 / EPTCS.318.14
[39] Aleks Kissinger en John van de Wetering. Het aantal niet-Clifford-poorten in kwantumcircuits verminderen. Physical Review A, Deel 102-2, 102: 022406, 8 2020b. 10.1103 / PhysRevA.102.022406.
https: / / doi.org/ 10.1103 / PhysRevA.102.022406
[40] Vadym Kliuchnikov en Dmitri Maslov. Optimalisatie van Clifford-circuits. Phys. Rev. A, 88: 052307, 2013. 10.1103 / PhysRevA.88.052307.
https: / / doi.org/ 10.1103 / PhysRevA.88.052307
[41] Anton Kotzig. Euleriaanse lijnen in eindige 4-valent grafieken en hun transformaties. In Colloqium on Graph Theory Tihany 1966, pagina's 219–230. Academic Press, 1968.
[42] Mehdi Mhalla en Simon Perdrix. Efficiënt optimale stromen vinden. In het 35e International Colloquium on Automata, Languages and Programming (ICALP), LNCS, volume 5125, pagina's 857-868, 2008. 10.1007 / 978-3-540-70575-8_70.
https://doi.org/10.1007/978-3-540-70575-8_70
[43] Mehdi Mhalla en Simon Perdrix. Grafiekstatussen, pivot minor en universaliteit van (X, Z) -metingen. International Journal of Unconventional Computing, 9 (1-2): 153-171, 2012. https: / / arxiv.org/ abs / 1202.6551.
arXiv: 1202.6551
[44] Mehdi Mhalla, Mio Murao, Simon Perdrix, Masato Someya en Peter S Turner. Welke grafiektoestanden zijn handig voor het verwerken van kwantuminformatie? In Conference on Quantum Computation, Communication, and Cryptography, pagina's 174–187. Springer, 2011. 10.1007 / 978-3-642-54429-3_12.
https://doi.org/10.1007/978-3-642-54429-3_12
[45] Jisho Miyazaki, Michal Hajdušek en Mio Murao. Analyse van de afweging tussen ruimtelijke en temporele bronnen voor op metingen gebaseerde kwantumberekeningen. Physical Review A, 91 (5): 052302, 2015. 10.1103 / physreva.91.052302.
https: / / doi.org/ 10.1103 / physreva.91.052302
[46] Kang Feng Ng en Quanlong Wang. Een universele aanvulling op de ZX-calculus. arXiv: 1706.09877, 2017.
arXiv: 1706.09877
[47] MA Nielsen en Isaac L. Chuang. Kwantumberekening en kwantuminformatie. Cambridge University Press, 2010. 10.1119 / 1.1463744.
https: / / doi.org/ 10.1119 / 1.1463744
[48] R. Raussendorf, DE Browne en HJ Briegel. Op metingen gebaseerde kwantumberekening op clustertoestanden. Physical Review A, 68 (2): 22312, 2003. 10.1103 / physreva.68.022312.
https: / / doi.org/ 10.1103 / physreva.68.022312
[49] Robert Raussendorf en Hans J. Briegel. Een eenrichtings-kwantumcomputer. Phys. Rev. Lett., 86: 5188-5191, 2001. 10.1103 / PhysRevLett.86.5188.
https: / / doi.org/ 10.1103 / PhysRevLett.86.5188
[50] M. Van den Nest, J. Dehaene en B. De Moor. Grafische beschrijving van de werking van lokale Clifford-transformaties op grafiektoestanden. Physical Review A, 69 (2): 9422, 2004. 10.1103 / physreva.69.022316.
https: / / doi.org/ 10.1103 / physreva.69.022316
[51] Renaud Vilmart. Een bijna minimale axiomatisering van ZX-calculus voor pure Qubit-kwantummechanica. In 2019 34e jaarlijkse ACM / IEEE-symposium over logica in computerwetenschappen (LICS), pagina's 1-10, 2019. 10.1109 / LICS.2019.8785765.
https: / / doi.org/ 10.1109 / LICS.2019.8785765
Geciteerd door
[1] Aleks Kissinger en John van de Wetering, "Reducing the number of non-Clifford gates in quantum circuits", Fysieke beoordeling A 102 2, 022406 (2020).
[2] Louis Lemonnier, John van de Wetering en Aleks Kissinger, "Hypergraph simplification: Linking the path-sum approach to the ZH-calculus", arXiv: 2003.13564.
[3] Chen Zhao en Xiao-Shan Gao, "Analyse van het onvruchtbare plateaufenomeen bij het trainen van kwantumneuraal netwerk met de ZX-calculus", arXiv: 2102.01828.
[4] Richard DP East, John van de Wetering, Nicholas Chancellor en Adolfo G. Grushin, "AKLT-staten als ZX-diagrammen: schematische redenering voor kwantumtoestanden", arXiv: 2012.01219.
[5] Miriam Backens, Aleks Kissinger, Hector Miller-Bakewell, John van de Wetering en Sal Wolffs, "Compleetheid van de ZH-calculus", arXiv: 2103.06610.
[6] John van de Wetering, "Quantum Theory from Principles, Quantum Software from Diagrams", arXiv: 2101.03608.
[7] Alexis Toumi, Richie Yeung en Giovanni de Felice, "Diagrammatische differentiatie voor Quantum Machine Learning", arXiv: 2103.07960.
[8] Bob Coecke, Dominic Horsman, Aleks Kissinger en Quanlong Wang, "afgestudeerden in de kwantummechanica van Kindergarden (... of hoe ik heb geleerd te stoppen met LEGO aan elkaar te lijmen en van de ZX-calculus te houden)", arXiv: 2102.10984.
Bovenstaande citaten zijn afkomstig van SAO / NASA ADS (laatst bijgewerkt met succes 2021-03-25 15:11:53). De lijst is mogelijk onvolledig omdat niet alle uitgevers geschikte en volledige citatiegegevens verstrekken.
Kon niet ophalen Door Crossref geciteerde gegevens tijdens laatste poging 2021-03-25 15:11:52: kon niet geciteerde gegevens voor 10.22331 / q-2021-03-25-421 niet ophalen van Crossref. Dit is normaal als de DOI recent is geregistreerd.
Dit artikel is gepubliceerd in Quantum onder de Creative Commons Naamsvermelding 4.0 Internationaal (CC BY 4.0) licentie. Het auteursrecht blijft berusten bij de oorspronkelijke houders van auteursrechten, zoals de auteurs of hun instellingen.
Coinsmart. Beste Bitcoin-beurs in Europa
Bron: https://quantum-journal.org/papers/q-2021-03-25-421/
