Kvantfördel i temporalt platt mätningsbaserad kvantberäkning

Kvantfördel i temporalt platt mätningsbaserad kvantberäkning

Tidsstämpel: 9 april 2024 7:15

Michael de Oliveira1,2,3, Luís S. Barbosa1,2,3, och Ernesto F. Galvão3,4

1University of Minho, Institutionen för datavetenskap, Braga, Portugal
2INESC TEC, Braga, Portugal
3International Iberian Nanotechnology Laboratory (INL) Av. Mestre Jose Veiga, 4715-330, Braga, Portugal
4Instituto de Física, Universidade Federal Fluminense Av. Tjej. Milton Tavares de Souza s/n, Niterói, RJ, 24210-340, Brasilien

Hitta det här uppsatsen intressant eller vill diskutera? Scite eller lämna en kommentar på SciRate.

Abstrakt

Flera klasser av kvantkretsar har visat sig ge en kvantberäkningsfördel under vissa antaganden. Studiet av allt mer begränsade klasser av kvantkretsar med förmåga till kvantfördelar motiveras av möjliga förenklingar i experimentella demonstrationer. I denna artikel studerar vi effektiviteten av mätbaserad kvantberäkning med en helt platt tidsordning av mätningar. Vi föreslår nya konstruktioner för deterministisk beräkning av godtyckliga booleska funktioner, med utgångspunkt från korrelationer som finns i multi-qubit Greenberger, Horne och Zeilinger (GHZ) tillstånd. Vi karakteriserar den nödvändiga mätkomplexiteten med hjälp av Clifford-hierarkin, och minskar också generellt antalet qubits som behövs i förhållande till tidigare konstruktioner. I synnerhet identifierar vi en familj av booleska funktioner för vilka deterministisk utvärdering med icke-adaptiv MBQC är möjlig, med kvantfördelar i bredd och antal grindar med avseende på klassiska kretsar.

Kvantfördel i temporalt platt mätningsbaserad kvantberäkning PlatoBlockchain Data Intelligence. Vertikal sökning. Ai.

Utvald bild: Den icke-adaptiva MBQC-modellen kan beskrivas av en specifik beräkningsarkitektur som är uppdelad i förberedelseprocessen för kvanttillstånd, mätrutinen och den tillhörande för- och postklassiska linjära bearbetningen (överst till vänster). Denna modell underlättar studiet av resurskrav för att utvärdera symmetriska booleska funktioner i termer av det asymptotiska antalet qubits och operationer som krävs (överst till höger). Dessa element avslöjar våra huvudresultat [nederst], som är artikulerade för klassiska standard- och kvantgrinduppsättningar och kretsbeskrivningar [nedre till vänster], som karakteriserar uppsättningen booleska funktioner som visar kvantfördelar med avseende på antalet grindar och bredden på kretsar (nederst till höger).

[Inbäddat innehåll]

Populär sammanfattning

Quantum computing lovar att leverera beräkningsmässiga fördelar med avseende på de bästa klassiska algoritmerna för många uppgifter. Rigorösa resultat som kvantifierar denna fördel är sällsynta och hjälper till att fokusera forskningen på de avgörande kvantresurserna som ger bättre än klassisk prestanda. Denna kvantfördel kan hända med avseende på olika resurser: det totala antalet grindar som krävs, djupet på de resulterande kretsarna eller storleken på minnet som används (känd som kretsbredd).

I detta arbete analyserar vi utvärderingen av booleska funktioner, något som kvantdatorer kan göra med hjälp av de korrelerade resultaten av mätningar på intrasslade Greenberger-Horne-Zeilinger (GHZ) tillstånd av många qubits. Denna variant av mätningsbaserad kvantberäkning kräver ingen adaptivitet, så alla kvantbitar kan mätas samtidigt. Denna platta tidsstruktur av beräkningsprocessen resulterar i vissa fall i mycket ekonomiska kvantkretsar. Vi identifierar egenskaperna hos en boolesk funktion som avgör hur många qubits som behövs, och den nödvändiga mätprecisionen. För en viss familj av booleska funktioner visar vi att det finns en rigorös fördel i bredd och antal grindar med avseende på motsvarande familj av klassiska kretsar. I framtiden kan våra tekniker hjälpa till att ta fram bättre sätt att använda kvantresurser även för adaptiva kretsar som visar mer beräkningsexpressivitet.

► BibTeX-data

► Referenser

[1] Scott Aaronson, DeVon Ingram och William Kretschmer. "The Acrobatics of BQP". I Shachar Lovett, redaktör, 37th Computational Complexity Conference (CCC 2022). Volym 234 av Leibniz International Proceedings in Informatics (LIPIcs), sidorna 20:1–20:17. Dagstuhl, Tyskland (2022). Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
https: / / doi.org/ 10.4230 / LIPIcs.CCC.2022.20

[2] Richard Jozsa och Noah Linden. "Om trasslingens roll i kvantberäkningshastigheten". Proceedings of the Royal Society of London. Serie A: Mathematical, Physical and Engineering Sciences 459, 2011–2032 (2003).
https: / / doi.org/ 10.1098 / rspa.2002.1097

[3] Mark Howard, Joel Wallman, Victor Veitch och Joseph Emerson. "Kontextualitet tillhandahåller 'magin' för kvantberäkningar". Nature 510, 351–355 (2014).
https: / / doi.org/ 10.1038 / nature13460

[4] Juan Bermejo-Vega, Nicolas Delfosse, Dan E. Browne, Cihan Okej och Robert Raussendorf. "Kontextualitet som en resurs för modeller för kvantberäkning med qubits". Phys. Rev. Lett. 119, 120505 (2017).
https: / / doi.org/ 10.1103 / PhysRevLett.119.120505

[5] Ernesto F. Galvão. "Diskreta wigner-funktioner och kvantberäkningshastighet". Phys. Rev. A 71, 042302 (2005).
https: / / doi.org/ 10.1103 / PhysRevA.71.042302

[6] A. Mari och J. Eisert. "Positiva wigner-funktioner gör klassisk simulering av kvantberäkning effektiv". Phys. Rev. Lett. 109, 230503 (2012).
https: / / doi.org/ 10.1103 / PhysRevLett.109.230503

[7] Lov K. Grover. "Fördelarna med superposition". Science 280, 228-228 (1998).
https: / / doi.org/ 10.1126 / science.280.5361.228

[8] Robert Raussendorf och Hans J. Briegel. "En enkelriktad kvantdator". Phys. Rev. Lett. 86, 5188–5191 (2001).
https: / / doi.org/ 10.1103 / PhysRevLett.86.5188

[9] Maarten Van den Nest, Akimasa Miyake, Wolfgang Dür och Hans J. Briegel. "Universella resurser för mätningsbaserad kvantberäkning". Phys. Rev. Lett. 97, 150504 (2006).
https: / / doi.org/ 10.1103 / PhysRevLett.97.150504

[10] Janet Anders och Dan E. Browne. "Korrelationers beräkningskraft". Phys. Rev. Lett. 102, 050502 (2009).
https: / / doi.org/ 10.1103 / PhysRevLett.102.050502

[11] Vincent Danos och Elham Kashefi. "Determinism i envägsmodellen". Phys. Rev. A 74, 052310 (2006).
https: / / doi.org/ 10.1103 / PhysRevA.74.052310

[12] Daniel E Browne, Elham Kashefi, Mehdi Mhalla och Simon Perdrix. "Generaliserat flöde och determinism i mätningsbaserad kvantberäkning". New Journal of Physics 9, 250 (2007).
https:/​/​doi.org/​10.1088/​1367-2630/​9/​8/​250

[13] Michael J Bremner, Ashley Montanaro och Dan J Shepherd. "Genomsnittlig fallkomplexitet kontra ungefärlig simulering av pendlingskvantberäkningar". Phys. Rev. Lett. 117, 080501 (2016).
https: / / doi.org/ 10.1103 / PhysRevLett.117.080501

[14] Matty J. Hoban, Joel J. Wallman, Hussain Anwar, Naïri Usher, Robert Raussendorf och Dan E. Browne. "Mätningsbaserad klassisk beräkning". Phys. Rev. Lett. 112, 140505 (2014).
https: / / doi.org/ 10.1103 / PhysRevLett.112.140505

[15] Michael J. Bremner, Ashley Montanaro och Dan J. Shepherd. "Att uppnå kvantöverlägsenhet med glesa och bullriga pendlingskvantberäkningar". Quantum 1, 8 (2017).
https:/​/​doi.org/​10.22331/​q-2017-04-25-8

[16] Leonardo Novo, Juani Bermejo-Vega och Raúl García-Patrón. "Kvantfördel från energimätningar av kvantsystem med många kroppar". Quantum 5, 465 (2021).
https:/​/​doi.org/​10.22331/​q-2021-06-02-465

[17] Masahito Hayashi och Yuki Takeuchi. "Verifiering av pendlingskvantberäkningar via trohetsuppskattning av viktade graftillstånd". New Journal of Physics 21, 93060 (2019).
https:/​/​doi.org/​10.1088/​1367-2630/​ab3d88

[18] Juan Bermejo-Vega, Dominik Hangleiter, Martin Schwarz, Robert Raussendorf och Jens Eisert. "Arkitekturer för kvantsimulering som visar en kvanthastighet". Phys. Rev. X 8, 021010 (2018).
https: / / doi.org/ 10.1103 / PhysRevX.8.021010

[19] Jacob Miller, Stephen Sanders och Akimasa Miyake. "Kvantöverlägsenhet i konstanttidsmätningsbaserad beräkning: En enhetlig arkitektur för sampling och verifiering". Phys. Rev. A 96, 062320 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.96.062320

[20] Matty J Hoban, Earl T Campbell, Klearchos Loukopoulos och Dan E Browne. "Icke-adaptiv mätningsbaserad kvantberäkning och multiparts Bell-ojämlikheter". New Journal of Physics 13, 23014 (2011).
https:/​/​doi.org/​10.1088/​1367-2630/​13/​2/​023014

[21] Ryuhei Mori. "Periodisk Fourier-representation av booleska funktioner". Kvantinformation. Comput. 19, 392–412 (2019). URL: https://​/​dl.acm.org/​doi/​abs/​10.5555/​3370251.3370253.
https: / / dl.acm.org/ doi / abs / 10.5555 / 3370251.3370253

[22] Markus Frembs, Sam Roberts, Earl T Campbell och Stephen D Bartlett. "Hierarkier av resurser för mätningsbaserad kvantberäkning". New Journal of Physics 25, 013002 (2023).
https://​/​doi.org/​10.1088/​1367-2630/​acaee2

[23] Jelena Mackeprang, Daniel Bhatti, Matty J Hoban och Stefanie Barz. "Kraften med qutrits för icke-adaptiv mätningsbaserad kvantberäkning". New Journal of Physics 25, 073007 (2023).
https://​/​doi.org/​10.1088/​1367-2630/​acdf77

[24] Daniel Collins, Nicolas Gisin, Sandu Popescu, David Roberts och Valerio Scarani. "Bell-Type Ojämlikheter för att upptäcka sann $mathit{n}$-Body Nonseparability". Phys. Rev. Lett. 88, 170405 (2002).
https: / / doi.org/ 10.1103 / PhysRevLett.88.170405

[25] Nicolas Brunner, Daniel Cavalcanti, Stefano Pironio, Valerio Scarani och Stephanie Wehner. "Block nonlocality". Rev. Mod. Phys. 86, 419–478 (2014).
https: / / doi.org/ 10.1103 / RevModPhys.86.419

[26] Dmitrijs Kravčenko. "Kvantspel, kvanttillstånd, deras egenskaper och tillämpningar". Doktorsavhandling. Latvijas Universitāte. (2013).

[27] William Slofstra. "Lägre gränser för förvecklingen som behövs för att spela XOR icke-lokala spel". Journal of Mathematical Physics 52, 102202 (2011).
https: / / doi.org/ 10.1063 / 1.3652924

[28] Andris Ambainis, Jānis Iraids, Dmitry Kravchenko och Madars Virza. "Fördel med kvantstrategier i slumpmässiga symmetriska xor-spel". I Antonín Kučera, Thomas A. Henzinger, Jaroslav Nešetřil, Tomáš Vojnar och David Antoš, redaktörer, Mathematical and Engineering Methods in Computer Science. Sidorna 57–68. Berlin, Heidelberg (2013). Springer Berlin Heidelberg.
https:/​/​doi.org/​10.1007/​978-3-642-36046-6_7

[29] Andris Ambainis och Janis Iraids. "Provable Advantage for Quantum Strategies in Random Symmetric XOR Games". I Simone Severini och Fernando Brandao, redaktörer, 8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013). Volym 22 av Leibniz International Proceedings in Informatics (LIPIcs), sidorna 146–156. Dagstuhl, Tyskland (2013). Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
https: / ⠀ </ ⠀ <doi.org/†<10.4230 / ⠀ <LIPIcs.TQC.2013.146

[30] Samuel Marcovitch och Benni Reznik. "Konsekvenser av kommunikationskomplexitet i flerpartisystem". Phys. Rev. A 77, 032120 (2008).
https: / / doi.org/ 10.1103 / PhysRevA.77.032120

[31] Marcin Pawłowski, Tomasz Paterek, Dagomir Kaszlikowski, Valerio Scarani, Andreas Winter och Marek Żukowski. "Informationskausalitet som en fysisk princip". Nature 461, 1101–1104 (2009).
https: / / doi.org/ 10.1038 / nature08400

[32] Sandu Popescu och Daniel Rohrlich. "Quantum nonlocality som ett axiom". Foundations of Physics 24, 379–385 (1994).
https: / / doi.org/ 10.1007 / BF02058098

[33] Jonathan Barrett, Noah Linden, Serge Massar, Stefano Pironio, Sandu Popescu och David Roberts. "Icke-lokala korrelationer som en informationsteoretisk resurs". Phys. Rev. A 71, 022101 (2005).
https: / / doi.org/ 10.1103 / PhysRevA.71.022101

[34] AA Razborov. "Kvantkommunikationskomplexitet för symmetriska predikat". Izvestiya: Mathematics 67, 145 (2003).
https:/​/​doi.org/​10.1070/​IM2003v067n01ABEH000422

[35] Zhiqiang Zhang och Yaoyun Shi. "Kommunikationskomplexiteter för symmetriska XOR-funktioner". Quantum Information and Computation 9, 255–263 (2009). URL: https://​/​dl.acm.org/​doi/​abs/​10.5555/​2011781.2011786.
https: / / dl.acm.org/ doi / abs / 10.5555 / 2011781.2011786

[36] Pierre Botteron. "Icke-lokala boxar och kommunikationskomplexitet". Magisteruppsats. Université Paul Sabatier Toulouse III. (2022). URL: https://​/​pierre-botteron.github.io/​Articles/​2022-06-MSc-Thesis.pdf.
https://​/​pierre-botteron.github.io/​Articles/​2022-06-MSc-Thesis.pdf

[37] Kwangil Bae och Wonmin Son. "Generaliserade icke-lokalitetskriterier under korrelationssymmetri". Phys. Rev. A 98, 022116 (2018).
https: / / doi.org/ 10.1103 / PhysRevA.98.022116

[38] Markus Frembs, Sam Roberts och Stephen D Bartlett. "Kontextualitet som en resurs för mätningsbaserad kvantberäkning bortom qubits". New Journal of Physics 20, 103011 (2018).
https: / / doi.org/ 10.1088 / 1367-2630 / aae3ad

[39] Sergey Bravyi, David Gosset och Robert König. "Kvantfördel med grunda kretsar". Science 362, 308–311 (2018).
https: / / doi.org/ 10.1126 / science.aar3106

[40] Daniel Grier och Luke Schaeffer. "Interactive Shallow Clifford Circuits: Quantum Advantage against NC¹ and Beyond". I samband med det 52:a årliga ACM SIGACT-symposiet om datorteori. Sidorna 875–888. STOC 2020New York, NY, USA (2020). Föreningen för Datormaskiner.
https: / / doi.org/ 10.1145 / 3357713.3384332

[41] Libor Caha, Xavier Coiteux-Roy och Robert Koenig. "Single-qubit gate teleportation ger en kvantfördel" (2022). arXiv:2209.14158.
arXiv: 2209.14158

[42] François Le Gall. "Average-Case Quantum Advantage med grunda kretsar". I Amir Shpilka, redaktör, 34th Computational Complexity Conference (CCC 2019). Volym 137 av Leibniz International Proceedings in Informatics (LIPIcs), sidorna 21:1—-21:20. Dagstuhl, Tyskland (2019). Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
https: / / doi.org/ 10.4230 / LIPIcs.CCC.2019.21

[43] Matthew Coudron, Jalex Stark och Thomas Vidick. "Handelsort för tid: certifierbar slumpmässighet från lågdjupa kretsar". Kommunikationer i matematisk fysik 382, ​​49–86 (2021).
https: / / doi.org/ 10.1007 / s00220-021-03963-w

[44] Sergey Bravyi, David Gosset, Robert König och Marco Tomamichel. "Kvantfördel med bullriga grunda kretsar". Nature Physics 16, 1040–1045 (2020).
https: / / doi.org/ 10.1038 / s41567-020-0948-z

[45] Atsuya Hasegawa och François Le Gall. "Quantum Advantage med grunda kretsar under godtycklig korruption". I Hee-Kap Ahn och Kunihiko Sadakane, redaktörer, 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Volym 212 av Leibniz International Proceedings in Informatics (LIPIcs), sidorna 74:1–74:16. Dagstuhl, Tyskland (2021). Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
https://doi.org/ 10.4230/LIPIcs.ISAAC.2021.74

[46] Adam Bene Watts, Robin Kothari, Luke Schaeffer och Avisay Tal. "Exponentiell separation mellan grunda kvantkretsar och obegränsade fan-in grunda klassiska kretsar". I samband med det 51:a årliga ACM SIGACT-symposiet om datorteori. Sidorna 515–526. STOC 2019New York, NY, USA (2019). Föreningen för Datormaskiner.
https: / / doi.org/ 10.1145 / 3313276.3316404

[47] Natalie Parham. "Om kraften och begränsningarna hos grunda kvantkretsar". Magisteruppsats. University of Waterloo. (2022). URL: https://​/​uwspace.uwaterloo.ca/​handle/​10012/​18702.
https://uwspace.uwaterloo.ca/ handtag/10012/18702

[48] Dmitri Maslov, Jin-Sung Kim, Sergey Bravyi, Theodore J Yoder och Sarah Sheldon. "Kvantfördel för beräkningar med begränsat utrymme". Nature Physics 17, 894–897 (2021).
https:/​/​doi.org/​10.1038/​s41567-021-01271-7

[49] Farid Ablayev, Aida Gainutdinova, Marek Karpinski, Cristopher Moore och Christopher Pollett. "Om beräkningskraften hos probabilistiska och kvantförgreningsprogram". Information and Computation 203, 145–162 (2005).
https: / / doi.org/ 10.1016 / j.ic.2005.04.003

[50] D Shepherd och MJ Bremner. "Temporärt ostrukturerad kvantberäkning". Proceedings of the Royal Society of London Series A 465, 1413–1439 (2009).
https: / / doi.org/ 10.1098 / rspa.2008.0443

[51] Daniel M Greenberger, Michael A Horne och Anton Zeilinger. "Going Beyond Bell's Theorem". I Menas Kafatos, redaktör, Bell's Theorem, Quantum Theory and Conceptions of the Universe. Sidorna 69–72. Dordrecht (1989). Springer Nederländerna.
https:/​/​doi.org/​10.1007/​978-94-017-0849-4_10

[52] Diogo Cruz, Romain Fournier, Fabien Gremion, Alix Jeannerot, Kenichi Komagata, Tara Tosic, Jarla Thiesbrummel, Chun Lam Chan, Nicolas Macris, Marc-André Dupertuis och Clément Javerzac-Galy. "Effektiva kvantalgoritmer för GHZ- och W-tillstånd och implementering på IBM Quantum Computer". Advanced Quantum Technologies 2, 1900015 (2019).
https: / / doi.org/ 10.1002 / qute.201900015

[53] RF Werner och MM Wolf. "All-multipartite bell-correlation ojämlikheter för två dikotoma observerbara per plats". Phys. Rev. A 64, 032112 (2001).
https: / / doi.org/ 10.1103 / PhysRevA.64.032112

[54] Ryan O'Donnell. "Analys av booleska funktioner". Cambridge University Press. (2014). url: http://​/​www.cs.cmu.edu/​ ./​odonnell/​papers/​Analysis-of-Boolean-Functions-by-Ryan-ODonnell.pdf.
http://​/​www.cs.cmu.edu/​~./​odonnell/​papers/​Analysis-of-Boolean-Functions-by-Ryan-ODonnell.pdf

[55] Anastasiya Chistopolskaya och Vladimir V. Podolskii. "Parity Decision Tree Complexity is Greater Than Granularity" (2018). arXiv:1810.08668.
arXiv: 1810.08668

[56] A Canteaut och M Videau. "Symmetriska booleska funktioner". IEEE Transactions on Information Theory 51, 2791–2811 (2005).
https: / / doi.org/ 10.1109 / TIT.2005.851743

[57] Larry J Stockmeyer. "Om kombinationskomplexiteten hos vissa symmetriska booleska funktioner". Matematisk systemteori 10, 323–336 (1976).
https: / / doi.org/ 10.1007 / BF01683282

[58] RF Arnold och MA Harrison. "Algebraiska egenskaper för symmetriska och delvis symmetriska booleska funktioner". IEEE-transaktioner på elektroniska datorer EC-12, 244–251 (1963).
https://​/​doi.org/​10.1109/​PGEC.1963.263535

[59] An Braeken och Bart Preneel. "Om den algebraiska immuniteten för symmetriska booleska funktioner". I Subhamoy Maitra, CE Veni Madhavan, och Ramarathnam Venkatesan, redaktörer, Progress in Cryptology – INDOCRYPT 2005. Volym 3797 av Lecture Notes in Computer Science, sidorna 35–48. Berlin, Heidelberg (2005). Springer Berlin Heidelberg.
https: / / doi.org/ 10.1007 / 11596219_4

[60] Harry Buhrman och Ronald de Wolf. "Komplexitetsmått och beslutsträdskomplexitet: en undersökning". Teoretisk datavetenskap 288, 21–43 (2002).
https:/​/​doi.org/​10.1016/​S0304-3975(01)00144-X

[61] Matthew Amy, Dmitri Maslov, Michele Mosca och Martin Roetteler. "En Meet-in-the-Middle-algoritm för snabb syntes av djupoptimala kvantkretsar". IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems 32, 818–830 (2013).
https: / / doi.org/ 10.1109 / TCAD.2013.2244643

[62] VV Shende, SS Bullock och IL Markov. "Syntes av kvantlogiska kretsar". IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems 25, 1000–1010 (2006).
https: / / doi.org/ 10.1109 / TCAD.2005.855930

[63] Juha J Vartiainen, Mikko Möttönen och Martti M Salomaa. "Effektiv nedbrytning av Quantum Gates". Phys. Rev. Lett. 92, 177902 (2004).
https: / / doi.org/ 10.1103 / PhysRevLett.92.177902

[64] Bei Zeng, Xie Chen och Isaac L Chuang. "Semi-Clifford operationer, struktur av $mathcal{C}_{k}$ hierarki och grindkomplexitet för feltolerant kvantberäkning". Phys. Rev. A 77, 042313 (2008).
https: / / doi.org/ 10.1103 / PhysRevA.77.042313

[65] Gary J Mooney, Charles D Hill och Lloyd CL Hollenberg. "Kostnadsoptimal en-qubit-grindsyntes i Clifford-hierarkin". Quantum 5, 396 (2021).
https:/​/​doi.org/​10.22331/​q-2021-02-15-396

[66] Nadish de Silva. "Effektiv quantum gate teleportation i högre dimensioner". Proceedings of the Royal Society A 477, 20200865 (2021).
https: / / doi.org/ 10.1098 / rspa.2020.0865

[67] Daniel Gottesman och Isaac L Chuang. "Demonstrera lönsamheten för universell kvantberäkning med hjälp av teleportering och en-qubit-operationer". Nature 402, 390–393 (1999).
https: / / doi.org/ 10.1038 / 46503

[68] Daniel Gottesman. "The Heisenberg representation of Quantum Computers" (1998). arXiv:quant-ph/​9807006.
arXiv: kvant-ph / 9807006

[69] Vadym Kliuchnikov, Dmitri Maslov och Michele Mosca. "Snabb och effektiv exakt syntes av single-qubit unitaries genererade av clifford och t-gates". Kvantinformation. Comput. 13, 607–630 (2013). URL: https://​/​dl.acm.org/​doi/​abs/​10.5555/​2535649.2535653.
https: / / dl.acm.org/ doi / abs / 10.5555 / 2535649.2535653

[70] Nicolas Brunner, James Sharam och Tamás Vértesi. "Testa strukturen av multipartite intrassling med bell ojämlikheter". Phys. Rev. Lett. 108, 110501 (2012).
https: / / doi.org/ 10.1103 / PhysRevLett.108.110501

[71] Julia Kempe, Hirotada Kobayashi, Keiji Matsumoto, Ben Toner och Thomas Vidick. "Entangled Games är svåra att uppskatta". SIAM Journal on Computing 40, 848–877 (2011).
https: / / doi.org/ 10.1137 / 090751293

[72] Yihui Quek, Eneet Kaur och Mark M. Wilde. "Multivariat spåruppskattning i konstant kvantdjup". Quantum 8, 1220 (2024).
https:/​/​doi.org/​10.22331/​q-2024-01-10-1220

[73] Peter Selinger. "Effektiv Clifford+T Approximation of Single-Qubit Operators". Kvantinformation. Comput. 15, 159–180 (2015).

[74] Vadym Kliuchnikov, Dmitri Maslov och Michele Mosca. "Praktisk approximation av enkel-Qubit-enheter av Single-Qubit Quantum Clifford och T-kretsar". IEEE-transaktioner på datorer 65, 161–172 (2016).
https: / / doi.org/ 10.1109 / TC.2015.2409842

[75] Neil J Ross. "Optimal ancilla-fri CLIFFORD+V Approximation av Z-rotationer". Kvantinformation. Comput. 15, 932–950 (2015). URL: https://​/​dl.acm.org/​doi/​abs/​10.5555/​2871350.2871354.
https: / / dl.acm.org/ doi / abs / 10.5555 / 2871350.2871354

[76] Ethan Bernstein och Umesh Vazirani. "Kvantkomplexitetsteori". I handlingar av det tjugofemte årliga ACM-symposiet om datorteori. Sidorna 11–20. STOC '93New York, NY, USA (1993). Föreningen för Datormaskiner.
https: / / doi.org/ 10.1145 / 167088.167097

[77] Alex Bocharov, Martin Roetteler och Krysta M Svore. "Effektiv syntes av probabilistiska kvantkretsar med reserv". Phys. Rev. A 91, 052317 (2015).
https: / / doi.org/ 10.1103 / PhysRevA.91.052317

[78] Alex Bocharov, Martin Roetteler och Krysta M Svore. "Effektiv syntes av universella kvantkretsar som upprepas fram till framgång". Phys. Rev. Lett. 114, 080502 (2015).
https: / / doi.org/ 10.1103 / PhysRevLett.114.080502

[79] Ingo Wegener. "Komplexiteten hos booleska funktioner". John Wiley $&$ Sons, Inc. USA (1987).

[80] Heribert Vollmer. "Introduktion till kretskomplexitet: ett enhetligt tillvägagångssätt". Springer Publishing Company, Incorporated. (2010). 1:a upplagan. URL: https://​/​link.springer.com/​book/​10.1007/​978-3-662-03927-4.
https:/​/​link.springer.com/​book/​10.1007/​978-3-662-03927-4

[81] R Smolensky. "Algebraiska metoder i teorin om nedre gränser för boolesk kretskomplexitet". I Proceedings of the nittonde årliga ACM Symposium on Theory of Computing. Sidorna 77–82. STOC '87 New York, NY, USA (1987). Föreningen för Datormaskiner.
https: / / doi.org/ 10.1145 / 28395.28404

[82] Jaikumar Radhakrishnan. "Bättre gränser för tröskelformler". I [1991] Proceedings 32nd Annual Symposium of Foundations of Computer Science. Sidorna 314–323. IEEE Computer Society (1991).
https: / / doi.org/ 10.1109 / SFCS.1991.185384

[83] Michael J Fischer, Albert R Meyer och Michael S Paterson. "$Omega(Nlog n)$ Nedre gränser för längden på booleska formler". SIAM J. Comput. 11, 416-427 (1982).
https: / / doi.org/ 10.1137 / 0211033

[84] Sanjeev Arora och Boaz Barak. "Computational Complexity: A Modern Approach". Cambridge University Press. USA (2009). 1:a upplagan. URL: https://​/​dl.acm.org/​doi/​abs/​10.5555/​1540612.
https: / / dl.acm.org/ doi / abs / 10.5555 / 1540612

[85] Scott Aaronson. "Hur mycket struktur behövs för enorma kvanthastigheter?" (2022). arXiv:2209.06930.
arXiv: 2209.06930

[86] David A Barrington. "Bounded-width polynom-storlek förgreningsprogram känner igen exakt de språken i NC1". Journal of Computer and System Sciences 38, 150–164 (1989).
https:/​/​doi.org/​10.1016/​0022-0000(89)90037-8

[87] Scott Aaronson och Alex Arkhipov. "Den linjära optikens beräkningskomplexitet". I Proceedings of the Forty-Thirth Annual ACM Symposium on Theory of Computing. Sidorna 333–342. STOC '11New York, NY, USA (2011). Föreningen för Datormaskiner.
https: / / doi.org/ 10.1145 / 1993636.1993682

[88] Peter W Shor. "Polynom-tidsalgoritmer för primfaktorisering och diskreta logaritmer på en kvantdator". SIAM Review 41, 303–332 (1999).
https: / / doi.org/ 10.1137 / S0036144598347011

[89] Daniel R Simon. "Om kraften i kvantberäkning". SIAM Journal on Computing 26, 1474–1483 (1997).
https: / / doi.org/ 10.1137 / S0097539796298637

[90] Gilles Brassard, Harry Buhrman, Noah Linden, André Allan Méthot, Alain Tapp och Unger Falk. "Begränsning för icke-lokalitet i vilken värld som helst där kommunikationskomplexitet inte är trivial". Phys. Rev. Lett. 96, 250401 (2006).
https: / / doi.org/ 10.1103 / PhysRevLett.96.250401

[91] Wim van Dam. "Otroliga konsekvenser av superstark icke-lokalitet". Natural Computing 12, 9–12 (2013).
https:/​/​doi.org/​10.1007/​s11047-012-9353-6

[92] Matthew Amy och Michele Mosca. "T-Count-optimering och Reed-Muller-koder". IEEE Transactions on Information Theory 65, 4771–4784 (2019).
https: / / doi.org/ 10.1109 / TIT.2019.2906374

[93] Peter Bürgisser, Michael Clausen och Mohammad A Shokrollahi. "Algebraisk komplexitetsteori". Volym 315. Springer Science & Business Media. (2013). URL: https://​/​dl.acm.org/​doi/​abs/​10.5555/​1965416.
https: / / dl.acm.org/ doi / abs / 10.5555 / 1965416

[94] Guang Hao Low och Isaac L. Chuang. "Optimal Hamilton-simulering genom kvantsignalbehandling". Phys. Rev. Lett. 118, 010501 (2017).
https: / / doi.org/ 10.1103 / PhysRevLett.118.010501

[95] Jeongwan Haah. "Produktnedbrytning av periodiska funktioner i kvantsignalbehandling". Quantum 3, 190 (2019).
https:/​/​doi.org/​10.22331/​q-2019-10-07-190

[96] Scott Aaronson, Shalev Ben-David, Robin Kothari, Shravas Rao och Avisay Tal. "Grad vs. ungefärlig grad och kvantimplikationer av Huangs känslighetsteorem". I samband med det 53:e årliga ACM SIGACT-symposiet om datorteori. Sidorna 1330–1342. STOC 2021New York, NY, USA (2021). Föreningen för Datormaskiner.
https: / / doi.org/ 10.1145 / 3406325.3451047

[97] Hao Huang. "Inducerade subgrafer av hyperkuber och ett bevis på känslighetsförmodan". Annals of Mathematics 190, 949–955 (2019).
https: / / doi.org/ 10.4007 / annals.2019.190.3.6

[98] Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha och Juris Smotrovs. "Separationer i frågekomplexitet baserat på pekarfunktioner". J. ACM 64 (2017).
https: / / doi.org/ 10.1145 / 3106234

[99] Peter Høyer och Robert Špalek. "Kvantumkretsar med obegränsad fan-out". I Helmut Alt och Michel Habib, redaktörer, STACS 2003. Sidorna 234–246. Berlin, Heidelberg (2003). Springer Berlin Heidelberg.
https:/​/​doi.org/​10.1007/​3-540-36494-3_22

[100] Austin K Daniel, Yingyue Zhu, C Huerta Alderete, Vikas Buchemmavari, Alaina M Green, Nhung H Nguyen, Tyler G Thurtell, Andrew Zhao, Norbert M Linke och Akimasa Miyake. "Kvantberäkningsfördel intygad av icke-lokala spel med det cykliska klustertillståndet". Phys. Rev. Research 4, 033068 (2022).
https: / / doi.org/ 10.1103 / PhysRevResearch.4.033068

[101] Paul Herringer och Robert Raussendorf. "Klassificering av mätbaserad kvanttråd i stabilisator PEPS". Quantum 7, 1041 (2023).
https:/​/​doi.org/​10.22331/​q-2023-06-12-1041

[102] Abhishek Anand. "Om kraften hos interfolierade lågdjupa kvantkretsar och klassiska kretsar". Magisteruppsats. University of Waterloo. (2022). URL: https://​/​uwspace.uwaterloo.ca/​handle/​10012/​18805.
https://uwspace.uwaterloo.ca/ handtag/10012/18805

[103] John Preskill. "Quantum Computing i NISQ-eran och därefter". Quantum 2, 79 (2018).
https:/​/​doi.org/​10.22331/​q-2018-08-06-79

[104] Bülent Demirel, Weikai Weng, Christopher Thalacker, Matty Hoban och Stefanie Barz. "Korrelationer för beräkning och beräkning för korrelationer". npj Quantum Information 7, 1–8 (2021).
https:/​/​doi.org/​10.1038/​s41534-020-00354-2

[105] Manoranjan Swain, Amit Rai, Bikash K Behera och Prasanta K Panigrahi. "Experimentell demonstration av kränkningarna av Mermins och Svetlichnys ojämlikheter för W- och GHZ-stater". Quantum Information Processing 18, 218 (2019).
https:/​/​doi.org/​10.1007/​s11128-019-2331-5

[106] Bo Yang, Rudy Raymond, Hiroshi Imai, Hyungseok Chang och Hidefumi Hiraishi. "Testa skalbara klockojämlikheter för kvantgraftillstånd på ibm kvantenheter". IEEE Journal on Emerging and Selected Topics in Circuits and Systems 12, 638–647 (2022).
https://​/​doi.org/​10.1109/​JETCAS.2022.3201730

[107] F. Baccari, R. Augusiak, I. Šupić, J. Tura och A. Acín. "Skalbara klockolikheter för qubit-graftillstånd och robust självtestning". Phys. Rev. Lett. 124, 020402 (2020).
https: / / doi.org/ 10.1103 / PhysRevLett.124.020402

[108] Ken X Wei, Isaac Lauer, Srikanth Srinivasan, Neereja Sundaresan, Douglas T McClure, David Toyli, David C McKay, Jay M Gambetta och Sarah Sheldon. "Verifiera multipartite intrasslade Greenberger-Horne-Zeilinger-tillstånd via flera kvantkoherenser". Phys. Rev. A 101, 032343 (2020).
https: / / doi.org/ 10.1103 / PhysRevA.101.032343

[109] Wei-Jia Huang, Wei-Chen Chien, Chien-Hung Cho, Che-Chun Huang, Tsung-Wei Huang och Ching-Ray Chang. "Mermins ojämlikheter med flera qubits med ortogonala mätningar på IBM Q 53-qubit-system". Quantum Engineering 2, e45 (2020).
https://​doi.org/​10.1002/​que2.45

[110] Meron Sheffer, Daniel Azses och Emanuele G Dalla Torre. "Spela Quantum Nonlocal-spel med sex bullriga Qubits på molnet". Advanced Quantum Technologies 5, 2100081 (2022).
https: / / doi.org/ 10.1002 / qute.202100081

[111] Vedran Dunjko, Theodoros Kapourniotis och Elham Kashefi. "Quantum-Enhanced Secure Delegated Classical Computing". Kvantinformation. Comput. 16, 61–86 (2016).

[112] Stefanie Barz, Vedran Dunjko, Florian Schlederer, Merritt Moore, Elham Kashefi och Ian A. Walmsley. "Förbättrad delegerad datoranvändning med hjälp av koherens". Phys. Rev. A 93, 032339 (2016).
https: / / doi.org/ 10.1103 / PhysRevA.93.032339

[113] Marco Clementi, Anna Pappa, Andreas Eckstein, Ian A Walmsley, Elham Kashefi och Stefanie Barz. "Klassisk flerpartsberäkning med hjälp av kvantresurser". Physical Review A 96, 062317 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.96.062317

[114] Nasir Ahmed och Kamisetty Ramamohan Rao. "Walsh-hadamard transformation". Ortogonala transformer för digital signalbehandling. Sidorna 99–152. Springer (1975).

[115] Michael A Nielsen och Isaac L Chuang. "Quantum Computation and Quantum Information: 10th Anniversary Edition". Cambridge University Press. (2010).
https: / / doi.org/ 10.1017 / CBO9780511976667

[116] Philip Feinsilver och Jerzy Kocik. "Krawtchouk-polynom och krawtchouk-matriser". Sidorna 115–141. Senaste framsteg i tillämpad sannolikhet. Springer USA. Boston, MA (2005).
https:/​/​doi.org/​10.1007/​0-387-23394-6_5

[117] Philip Feinsilver och Rene Schott. "Krawtchouk transformerar och svänger". Bulletin of Mathematical Sciences Sidorna 1–19 (2018).
https:/​/​doi.org/​10.1007/​s13373-018-0132-2

[118] M. Stobińska, A. Buraczewski, M. Moore, WR Clements, JJ Renema, SW Nam, T. Gerrits, A. Lita, WS Kolthammer, A. Eckstein och IA Walmsley. "Kvantinterferens möjliggör konstant kvantinformationsbehandling". Science Advances 5, eaau9674 (2019).
https: / / doi.org/ 10.1126 / sciadv.aau9674

[119] Ravindran Kannan och Achim Bachem. "Polynomiska algoritmer för att beräkna Smith och Hermites normala former av en heltalsmatris". SIAM Journal on Computing 8, 499–507 (1979).
https: / / doi.org/ 10.1137 / 0208040

[120] Josh Alman och Virginia Vassilevska Williams. "En förfinad lasermetod och snabbare matrismultiplikation". I samband med det trettioandra årliga ACM-SIAM-symposiet om diskreta algoritmer. Sida 522–539. SODA '21USA (2021). Föreningen för industriell och tillämpad matematik.
https: / / doi.org/ 10.1137 / 1.9781611976465.32

Citerad av

Detta papper publiceras i Quantum under Creative Commons Attribution 4.0 International (CC BY 4.0) licens. Upphovsrätten kvarstår med de ursprungliga upphovsrättsinnehavarna som författarna eller deras institutioner.

Tidsstämpel:

Mer från Quantum Journal