Abstraqt: Analyse von Quantenschaltungen mittels abstrakter Stabilisatorsimulation

Abstraqt: Analyse von Quantenschaltungen mittels abstrakter Stabilisatorsimulation

Benjamin Bichsel, Anouk Paradis, Maximilian Baader und Martin Vechev

ETH Zürich, Schweiz

Findest du dieses Paper interessant oder möchtest du darüber diskutieren? Scite oder hinterlasse einen Kommentar zu SciRate.

Abstrakt

Die Stabilisatorsimulation kann eine wichtige Klasse von Quantenschaltungen, die ausschließlich aus Clifford-Gattern bestehen, effizient simulieren. Allerdings leiden alle existierenden Erweiterungen dieser Simulation auf beliebige Quantenschaltungen einschließlich Nicht-Clifford-Gattern unter einer exponentiellen Laufzeit.
Um dieser Herausforderung zu begegnen, präsentieren wir einen neuartigen Ansatz für eine effiziente Stabilisatorsimulation auf beliebigen Quantenschaltungen, allerdings auf Kosten der verlorenen Präzision. Unsere Schlüsselidee besteht darin, eine exponentielle Summendarstellung des Quantenzustands in einen einzigen $abstrakten$ Summanden zu komprimieren, der (mindestens) alle vorkommenden Summanden abdeckt. Dies ermöglicht uns die Einführung eines $textit{abstrakten Stabilisatorsimulators}$, der abstrakte Summanden effizient manipuliert, indem er die Wirkung von Schaltkreisoperationen, einschließlich Clifford-Gattern, Nicht-Clifford-Gattern und (internen) Messungen, übermäßig annähert.
Wir haben unseren abstrakten Simulator in einem Tool namens Abstraqt implementiert und experimentell gezeigt, dass Abstraqt Schaltungseigenschaften festlegen kann, die für bestehende Techniken unlösbar sind.

► BibTeX-Daten

► Referenzen

[1] Daniel Gottesmann. „Die Heisenberg-Darstellung von Quantencomputern“. Technischer Bericht arXiv:quant-ph/​9807006. arXiv (1998).
https://​/​doi.org/​10.48550/​arXiv.quant-ph/​9807006
arXiv: quant-ph / 9807006

[2] Scott Aaronson und Daniel Gottesman. „Verbesserte Simulation von Stabilisatorschaltungen“. Physical Review A 70, 052328 (2004).
https: / / doi.org/ 10.1103 / PhysRevA.70.052328

[3] Robert Rand, Aarthi Sundaram, Kartik Singhal und Brad Lackey. „Gottesman-Typen über die Clifford-Gruppe hinaus erweitern“. Im zweiten internationalen Workshop zu Programmiersprachen für Quantencomputing (PLANQC 2021). (2021). URL: https://​/​pldi21.sigplan.org/​details/​planqc-2021-papers/​9/​Extending-Gottesman-Types-Beyond-the-Clifford-Group.
https://​/​pldi21.sigplan.org/​details/​planqc-2021-papers/​9/​Extending-Gottesman-Types-Beyond-the-Clifford-Group

[4] Aleks Kissinger und John van de Wetering. „Simulation von Quantenschaltkreisen mit ZX-Kalkül reduzierten Stabilisatorzerlegungen“. Quantenwissenschaft und -technologie 7, 044001 (2022).
https:/​/​doi.org/​10.1088/​2058-9565/​ac5d20

[5] Sergey Bravyi, Dan Browne, Padraic Calpin, Earl Campbell, David Gosset und Mark Howard. „Simulation von Quantenschaltkreisen durch Zerlegungen niederrangiger Stabilisatoren“. Quantum 3, 181 (2019).
https:/​/​doi.org/​10.22331/​q-2019-09-02-181

[6] Hakop Pashayan, Oliver Reardon-Smith, Kamil Korzekwa und Stephen D. Bartlett. „Schnelle Schätzung von Ergebniswahrscheinlichkeiten für Quantenschaltungen“. PRX Quantum 3, 020361 (2022).
https: / / doi.org/ 10.1103 / PRXQuantum.3.020361

[7] „Klassische Simulation von Quantenschaltungen mit partieller und grafischer Stabilisatorzerlegung“. Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022).
https://​/​doi.org/​10.4230/​LIPICS.TQC.2022.5

[8] Patrick Cousot und Radhia Cousot. „Abstrakte Interpretation: Ein einheitliches Gittermodell für die statische Analyse von Programmen durch Konstruktion oder Approximation von Fixpunkten“. In Proceedings des 4. ACM SIGACT-SIGPLAN Symposiums zu Prinzipien von Programmiersprachen. Seiten 238–252. POPL '77New York, NY, USA (1977). ACM.
https: / / doi.org/ 10.1145 / 512950.512973

[9] Patrick Cousot und Radhia Cousot. „Abstrakte Interpretationsrahmen“. Journal of Logic and Computation 2, 511–547 (1992).
https://​/​doi.org/​10.1093/​logcom/​2.4.511

[10] Bruno Blanchet, Patrick Cousot, Radhia Cousot, Jérome Feret, Laurent Mauborgne, Antoine Miné, David Monniaux und Xavier Rival. „Ein statischer Analysator für große sicherheitskritische Software“. ACM SIGPLAN Notices 38, 196–207 (2003).
https: / / doi.org/ 10.1145 / 780822.781153

[11] Francesco Logozzo und Manuel Fähndrich. „Pentagons: Eine schwach relationale abstrakte Domäne zur effizienten Validierung von Array-Zugriffen“. Science of Computer Programming 75, 796–807 (2010).
https://​/​doi.org/​10.1016/​j.scico.2009.04.004

[12] Timon Gehr, Matthew Mirman, Dana Drachsler-Cohen, Petar Tsankov, Swarat Chaudhuri und Martin Vechev. „AI2: Sicherheits- und Robustheitszertifizierung neuronaler Netze mit abstrakter Interpretation“. Im Jahr 2018 IEEE Symposium on Security and Privacy (SP). Seiten 3–18. San Francisco, Kalifornien (2018). IEEE.
https: / / doi.org/ 10.1109 / SP.2018.00058

[13] Michael A. Nielsen und Isaac L. Chuang. „Quantenberechnung und Quanteninformation: Ausgabe zum 10-jährigen Jubiläum“. Cambridge University Press. (2010).
https: / / doi.org/ 10.1017 / CBO9780511976667

[14] Gadi Aleksandrowicz, Thomas Alexander, Panagiotis Barkoutsos, Luciano Bello, Yael Ben-Haim, David Bucher, Francisco Jose Cabrera-Hernández, Jorge Carballo-Franquis, Adrian Chen, Chun-Fu Chen, Jerry M. Chow, Antonio D. Córcoles-Gonzales , Abigail J. Cross, Andrew Cross, Juan Cruz-Benito, Chris Culver, Salvador De La Puente González, Enrique De La Torre, Delton Ding, Eugene Dumitrescu, Ivan Duran, Pieter Eendebak, Mark Everitt, Ismael Faro Sertage, Albert Frisch, Andreas Fuhrer, Jay Gambetta, Borja Godoy Gago, Juan Gomez-Mosquera, Donny Greenberg, Ikko Hamamura, Vojtech Havlicek, Joe Hellmers, Łukasz Herok, Hiroshi Horii, Shaohan Hu, Takashi Imamichi, Toshinari Itoko, Ali Javadi-Abhari, Naoki Kanazawa, Anton Karazeev, Kevin Krsulich, Peng Liu, Yang Luh, Yunho Maeng, Manoel Marques, Francisco Jose Martín-Fernández, Douglas T. McClure, David McKay, Srujan Meesala, Antonio Mezzacapo, Nikolaj Moll, Diego Moreda Rodríguez, Giacomo Nannicini, Paul Nation , Pauline Ollitrault, Lee James O'Riordan, Hanhee Paik, Jesús Pérez, Anna Phan, Marco Pistoia, Viktor Prutyanov, Max Reuter, Julia Rice, Abdón Rodríguez Davila, Raymond Harry Putra Rudy, Mingi Ryu, Ninad Sathaye, Chris Schnabel, Eddie Schoute, Kanav Setia, Yunong Shi, Adenilton Silva, Yukio Siraichi, Seyon Sivarajah, John A. Smolin, Mathias Soeken, Hitomi Takahashi, Ivano Tavernelli, Charles Taylor, Pete Taylour, Kenso Trabing, Matthew Treinish, Wes Turner, Desiree Vogt-Lee , Christophe Vuillot, Jonathan A. Wildstrom, Jessica Wilson, Erick Winston, Christopher Wood, Stephen Wood, Stefan Wörner, Ismail Yunus Akhalwaya und Christa Zoufal. „Qiskit: Ein Open-Source-Framework für Quantencomputing“ (2019).

[15] Charles R. Harris, K. Jarrod Millman, Stéfan J. van der Walt, Ralf Gommers, Pauli Virtanen, David Cournapeau, Eric Wieser, Julian Taylor, Sebastian Berg, Nathaniel J. Smith, Robert Kern, Matti Picus, Stephan Hoyer, Marten H. van Kerkwijk, Matthew Brett, Allan Haldane, Jaime Fernández del Río, Mark Wiebe, Pearu Peterson, Pierre Gérard-Marchant, Kevin Sheppard, Ty ler Reddy, Warren Weckesser, Hameer Abbasi, Christoph Gohlke und Travis E. Oliphant. „Array-Programmierung mit NumPy“. Natur 585, 357–362 (2020).
https:/​/​doi.org/​10.1038/​s41586-020-2649-2

[16] Siu Kwan Lam, Antoine Pitrou und Stanley Seibert. „Numba: ein LLVM-basierter Python-JIT-Compiler“. In Proceedings of the Second Workshop on the LLVM Compiler Infrastructure in HPC. Seiten 1–6. LLVM '15New York, NY, USA (2015). Verband für Rechenmaschinen.
https: / / doi.org/ 10.1145 / 2833157.2833162

[17] Craig Gidney. „Stim: ein schneller Stabilisatorschaltungssimulator“. Quantum 5, 497 (2021).
https:/​/​doi.org/​10.22331/​q-2021-07-06-497

[18] Henry S. Warren. „Hackers Freude“. Addison-Wesley-Profi. (2012). 2. Auflage.
https: / / doi.org/ 10.5555 / 2462741

[19] Aleks Kissinger und John van de Wetering. „PyZX: Groß angelegtes automatisiertes schematisches Denken“. In Bob Coecke und Matthew Leifer, Herausgeber, Proceedings 16th International Conference on Quantum Physics and Logic, Chapman University, Orange, CA, USA., 10.–14. Juni 2019. Band 318 von Electronic Proceedings in Theoretical Computer Science, Seiten 229–241. Open Publishing Association (2020).
https: / / doi.org/ 10.4204 / EPTCS.318.14

[20] Matthew Amy. „Auf dem Weg zur groß angelegten Funktionsüberprüfung universeller Quantenschaltkreise“. Electronic Proceedings in Theoretical Computer Science 287, 1–21 (2019).
https: / / doi.org/ 10.4204 / EPTCS.287.1

[21] Nengkun Yu und Jens Palsberg. „Quantenabstrakte Interpretation“. In Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation. Seiten 542–558. PLDI 2021New York, NY, USA (2021). Verband für Rechenmaschinen.
https: / / doi.org/ 10.1145 / 3453483.3454061

[22] Antoine Miné. „Schwach relationale numerische abstrakte Domänen“. Doktorarbeit (2004). URL: https://www-apr.lip6.fr/​mine/​these/​these-color.pdf.
https://​/​www-apr.lip6.fr/​~mine/​these/​these-color.pdf

[23] Simon Perdrix. „Quantenverschränkungsanalyse basierend auf abstrakter Interpretation“. In Proceedings des 15. Internationalen Symposiums zur statischen Analyse. Seiten 270–282. SAS '08Berlin, Heidelberg (2008). Springer-Verlag.
https:/​/​doi.org/​10.1007/​978-3-540-69166-2_18

[24] Kentaro Honda. „Analyse der Quantenverschränkung in Quantenprogrammen unter Verwendung des Stabilisatorformalismus“. Elektronische Verfahren in der Theoretischen Informatik 195 (2015).
https: / / doi.org/ 10.4204 / EPTCS.195.19

[25] Kesha Hietala, Robert Rand, Shih-Han Hung, Liyi Li und Michael Hicks. „Die Richtigkeit von Quantenprogrammen beweisen“. Leibniz International Proceedings in Informatics (LIPIcs) 193, 21:1–21:19 (2021).
https://​/​doi.org/​10.4230/​LIPIcs.ITP.2021.21

[26] Christophe Chareton, Sébastien Bardin, François Bobot, Valentin Perrelle und Benoît Valiron. „Ein automatisiertes deduktives Verifikations-Framework für Quantenprogramme zum Schaltungsaufbau“. In Programmiersprachen und -systemen. Seiten 148–177. Springer International Publishing (2021).
https:/​/​doi.org/​10.1007/​978-3-030-72019-3_6

[27] Mingsheng Ying, Shenggang Ying und Xiaodi Wu. „Invarianten von Quantenprogrammen: Charakterisierung und Erzeugung“. SIGPLAN Nicht. 52, 818–832 (2017).
https: / / doi.org/ 10.1145 / 3093333.3009840

Zitiert von

Konnte nicht abrufen Crossref zitiert von Daten während des letzten Versuchs 2023-11-20 15:19:03: Von Crossref konnten keine zitierten Daten für 10.22331 / q-2023-11-20-1185 abgerufen werden. Dies ist normal, wenn der DOI kürzlich registriert wurde. Auf SAO / NASA ADS Es wurden keine Daten zum Zitieren von Werken gefunden (letzter Versuch 2023-11-20 15:19:04).

Zeitstempel:

Mehr von Quantenjournal