1University of Minho, Institutt for informatikk, 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. Gal. Milton Tavares de Souza s/n, Niterói, RJ, 24210-340, Brasil
Finn dette papiret interessant eller vil diskutere? Scite eller legg igjen en kommentar på SciRate.
Abstrakt
Flere klasser av kvantekretser har vist seg å gi en kvanteberegningsfordel under visse forutsetninger. Studiet av stadig mer begrensede klasser av kvantekretser som er i stand til kvantefordeler er motivert av mulige forenklinger i eksperimentelle demonstrasjoner. I denne artikkelen studerer vi effektiviteten av målebasert kvanteberegning med en helt flat tidsmessig rekkefølge av målinger. Vi foreslår nye konstruksjoner for deterministisk beregning av vilkårlige boolske funksjoner, ved å trekke på korrelasjoner som er tilstede i multi-qubit Greenberger, Horne og Zeilinger (GHZ) tilstander. Vi karakteriserer den nødvendige målekompleksiteten ved å bruke Clifford-hierarkiet, og reduserer også generelt antall qubits som trengs i forhold til tidligere konstruksjoner. Spesielt identifiserer vi en familie av boolske funksjoner som deterministisk evaluering ved bruk av ikke-adaptiv MBQC er mulig, med kvantefordel i bredde og antall porter i forhold til klassiske kretser.
Utvalgt bilde: Den ikke-adaptive MBQC-modellen kan beskrives av en spesifikk beregningsarkitektur som er delt inn i forberedelsesprosessen for kvantetilstand, målerutinen og den tilhørende pre- og postklassiske lineære prosesseringen (øverst til venstre). Denne modellen letter studiet av ressurskrav for å evaluere symmetriske boolske funksjoner i form av det asymptotiske antallet qubits og operasjoner som kreves (øverst til høyre). Disse elementene avslører hovedresultatene våre [nederst], som er artikulert for standard klassiske og kvanteportsett og kretsbeskrivelser [nederst til venstre], som karakteriserer settet med boolske funksjoner som demonstrerer kvantefordeler med hensyn til antall porter og bredden på kretser (nederst til høyre).
[Innebygd innhold]
Populært sammendrag
I dette arbeidet analyserer vi evalueringen av boolske funksjoner, noe kvantedatamaskiner kan gjøre ved å bruke de korrelerte resultatene av målinger på entangled Greenberger-Horne-Zeilinger (GHZ) tilstander av mange qubits. Denne varianten av målebasert kvanteberegning krever ingen adaptivitet, så alle qubits kan måles samtidig. Denne flate tidsstrukturen til beregningsprosessen resulterer i noen tilfeller i svært økonomiske kvantekretser. Vi identifiserer egenskapene til en boolsk funksjon som bestemmer hvor mange qubits som trengs, og den nødvendige målingspresisjonen. For en bestemt familie av boolske funksjoner viser vi at det er en streng fordel i bredde og antall porter i forhold til den tilsvarende familien av klassiske kretser. I fremtiden kan teknikkene våre bidra til å utvikle bedre måter å bruke kvanteressurser på også for adaptive kretser som viser mer beregningsmessig ekspressivitet.
► BibTeX-data
► Referanser
[1] Scott Aaronson, DeVon Ingram og William Kretschmer. "Akrobatikken til BQP". I Shachar Lovett, redaktør, 37th Computational Complexity Conference (CCC 2022). Bind 234 av Leibniz International Proceedings in Informatics (LIPIcs), side 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 og Noah Linden. "Om sammenfiltringens rolle i kvanteberegningshastigheten". 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 og Joseph Emerson. "Kontekstualitet gir 'magien' for kvanteberegning". Nature 510, 351–355 (2014).
https: / / doi.org/ 10.1038 / nature13460
[4] Juan Bermejo-Vega, Nicolas Delfosse, Dan E. Browne, Cihan Okay og Robert Raussendorf. "Kontekstualitet som en ressurs for modeller for kvanteberegning med qubits". Phys. Rev. Lett. 119, 120505 (2017).
https: / / doi.org/ 10.1103 / PhysRevLett.119.120505
[5] Ernesto F. Galvão. "Diskrete wigner-funksjoner og kvanteberegningshastighet". Phys. Rev. A 71, 042302 (2005).
https: / / doi.org/ 10.1103 / PhysRevA.71.042302
[6] A. Mari og J. Eisert. "Positive wigner-funksjoner gjør klassisk simulering av kvanteberegning effektiv". Phys. Rev. Lett. 109, 230503 (2012).
https: / / doi.org/ 10.1103 / PhysRevLett.109.230503
[7] Kjærlighet K. Grover. "Fordelene med superposisjon". Science 280, 228-228 (1998).
https: / / doi.org/ 10.1126 / science.280.5361.228
[8] Robert Raussendorf og Hans J. Briegel. "En enveis kvantedatamaskin". 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 og Hans J. Briegel. "Universelle ressurser for målebasert kvanteberegning". Phys. Rev. Lett. 97, 150504 (2006).
https: / / doi.org/ 10.1103 / PhysRevLett.97.150504
[10] Janet Anders og Dan E. Browne. "Beregningskraft for korrelasjoner". Phys. Rev. Lett. 102, 050502 (2009).
https: / / doi.org/ 10.1103 / PhysRevLett.102.050502
[11] Vincent Danos og Elham Kashefi. "Determinisme i enveismodellen". Phys. Rev. A 74, 052310 (2006).
https: / / doi.org/ 10.1103 / PhysRevA.74.052310
[12] Daniel E Browne, Elham Kashefi, Mehdi Mhalla og Simon Perdrix. "Generalisert flyt og determinisme i målebasert kvanteberegning". New Journal of Physics 9, 250 (2007).
https://doi.org/10.1088/1367-2630/9/8/250
[13] Michael J Bremner, Ashley Montanaro og Dan J Shepherd. "Gjennomsnittlig sakskompleksitet versus omtrentlig simulering av pendlingskvanteberegninger". 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 og Dan E. Browne. "Målingsbasert klassisk beregning". Phys. Rev. Lett. 112, 140505 (2014).
https: / / doi.org/ 10.1103 / PhysRevLett.112.140505
[15] Michael J. Bremner, Ashley Montanaro og Dan J. Shepherd. "Oppnå kvanteoverlegenhet med sparsomme og støyende pendlingskvanteberegninger". Quantum 1, 8 (2017).
https://doi.org/10.22331/q-2017-04-25-8
[16] Leonardo Novo, Juani Bermejo-Vega og Raúl García-Patrón. "Kvantefordel fra energimålinger av kvantesystemer med mange kropper". Quantum 5, 465 (2021).
https://doi.org/10.22331/q-2021-06-02-465
[17] Masahito Hayashi og Yuki Takeuchi. "Bekrefte pendlende kvanteberegninger via trofasthetsestimering av vektede graftilstander". 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 og Jens Eisert. "Arkitekturer for kvantesimulering som viser en kvantehastighet". Phys. Rev. X 8, 021010 (2018).
https: / / doi.org/ 10.1103 / PhysRevX.8.021010
[19] Jacob Miller, Stephen Sanders og Akimasa Miyake. "Kvanteoverlegenhet i konstant-tidsmålingsbasert beregning: En enhetlig arkitektur for prøvetaking og verifisering". Phys. Rev. A 96, 062320 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.96.062320
[20] Matty J Hoban, Earl T Campbell, Klearchos Loukopoulos og Dan E Browne. "Ikke-adaptiv målebasert kvanteberegning og flerparts Bell-ulikheter". New Journal of Physics 13, 23014 (2011).
https://doi.org/10.1088/1367-2630/13/2/023014
[21] Ryuhei Mori. "Periodisk Fourier-representasjon av boolske funksjoner". Kvanteinformasjon. 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 og Stephen D Bartlett. "Hierarkier av ressurser for målebasert kvanteberegning". New Journal of Physics 25, 013002 (2023).
https:///doi.org/10.1088/1367-2630/acaee2
[23] Jelena Mackeprang, Daniel Bhatti, Matty J Hoban og Stefanie Barz. "Kraften til qutrits for ikke-adaptiv målebasert kvanteberegning". New Journal of Physics 25, 073007 (2023).
https:///doi.org/10.1088/1367-2630/acdf77
[24] Daniel Collins, Nicolas Gisin, Sandu Popescu, David Roberts og Valerio Scarani. "Bell-type ulikheter for å oppdage ekte $mathit{n}$-kroppsløshet". Phys. Rev. Lett. 88, 170405 (2002).
https: / / doi.org/ 10.1103 / PhysRevLett.88.170405
[25] Nicolas Brunner, Daniel Cavalcanti, Stefano Pironio, Valerio Scarani og Stephanie Wehner. "Bell ikke-lokalitet". Rev. Mod. Phys. 86, 419–478 (2014).
https: / / doi.org/ 10.1103 / RevModPhys.86.419
[26] Dmitrijs Kravčenko. "Kvantespill, kvantestater, deres egenskaper og applikasjoner". PhD-avhandling. Latvijas Universitāte. (2013).
[27] William Slofstra. "Nedre grenser for forviklingen som trengs for å spille XOR ikke-lokale spill". Journal of Mathematical Physics 52, 102202 (2011).
https: / / doi.org/ 10.1063 / 1.3652924
[28] Andris Ambainis, Jānis Iraids, Dmitry Kravchenko og Madars Virza. "Fordel med kvantestrategier i tilfeldige symmetriske xor-spill". I Antonín Kučera, Thomas A. Henzinger, Jaroslav Nešetřil, Tomáš Vojnar og David Antoš, redaktører, Mathematical and Engineering Methods in Computer Science. Side 57–68. Berlin, Heidelberg (2013). Springer Berlin Heidelberg.
https://doi.org/10.1007/978-3-642-36046-6_7
[29] Andris Ambainis og Janis Iraids. "Påviselig fordel for kvantestrategier i tilfeldige symmetriske XOR-spill". I Simone Severini og Fernando Brandao, redaktører, 8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013). Bind 22 av Leibniz International Proceedings in Informatics (LIPIcs), side 146–156. Dagstuhl, Tyskland (2013). Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
https: / / doi.org/ 10.4230 / LIPIcs.TQC.2013.146
[30] Samuel Marcovitch og Benni Reznik. "Implikasjoner av kommunikasjonskompleksitet i flerpartssystemer". 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 og Marek Żukowski. "Informasjonsårsakssammenheng som et fysisk prinsipp". Nature 461, 1101–1104 (2009).
https: / / doi.org/ 10.1038 / nature08400
[32] Sandu Popescu og Daniel Rohrlich. "Kvante-ikke-lokalitet som et aksiom". Foundations of Physics 24, 379–385 (1994).
https: / / doi.org/ 10.1007 / BF02058098
[33] Jonathan Barrett, Noah Linden, Serge Massar, Stefano Pironio, Sandu Popescu og David Roberts. "Ikke-lokale korrelasjoner som en informasjonsteoretisk ressurs". Phys. Rev. A 71, 022101 (2005).
https: / / doi.org/ 10.1103 / PhysRevA.71.022101
[34] AA Razborov. "Kvantekommunikasjonskompleksiteten til symmetriske predikater". Izvestiya: Mathematics 67, 145 (2003).
https://doi.org/10.1070/IM2003v067n01ABEH000422
[35] Zhiqiang Zhang og Yaoyun Shi. "Kommunikasjonskompleksiteten til symmetriske XOR-funksjoner". 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. "Ikke-lokale bokser og kommunikasjonskompleksitet". Masteroppgave. 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 og Wonmin Son. "Generaliserte ikke-lokalitetskriterier under korrelasjonssymmetrien". Phys. Rev. A 98, 022116 (2018).
https: / / doi.org/ 10.1103 / PhysRevA.98.022116
[38] Markus Frembs, Sam Roberts og Stephen D Bartlett. "Kontekstualitet som en ressurs for målebasert kvanteberegning utover qubits". New Journal of Physics 20, 103011 (2018).
https:///doi.org/10.1088/1367-2630/aae3ad
[39] Sergey Bravyi, David Gosset og Robert König. "Kvantefordel med grunne kretser". Science 362, 308–311 (2018).
https: / / doi.org/ 10.1126 / science.aar3106
[40] Daniel Grier og Luke Schaeffer. "Interactive Shallow Clifford Circuits: Quantum Advantage against NC¹ and Beyond". I Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing. Side 875–888. STOC 2020New York, NY, USA (2020). Foreningen for datamaskiner.
https: / / doi.org/ 10.1145 / 3357713.3384332
[41] Libor Caha, Xavier Coiteux-Roy og Robert Koenig. "Single-qubit gate teleportation gir en kvantefordel" (2022). arXiv:2209.14158.
arxiv: 2209.14158
[42] François Le Gall. "Gjennomsnittlig kvantefordel med grunne kretser". I Amir Shpilka, redaktør, 34th Computational Complexity Conference (CCC 2019). Bind 137 av Leibniz International Proceedings in Informatics (LIPIcs), side 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 og Thomas Vidick. "Handelslokalitet for tid: sertifiserbar tilfeldighet fra kretsløp med lav dybde". Kommunikasjon i matematisk fysikk 382, 49–86 (2021).
https: / / doi.org/ 10.1007 / s00220-021-03963-w
[44] Sergey Bravyi, David Gosset, Robert König og Marco Tomamichel. "Kvantefordel med støyende grunne kretser". Nature Physics 16, 1040–1045 (2020).
https: / / doi.org/ 10.1038 / s41567-020-0948-z
[45] Atsuya Hasegawa og François Le Gall. "Quantum Advantage med grunne kretser under vilkårlig korrupsjon". I Hee-Kap Ahn og Kunihiko Sadakane, redaktører, 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Bind 212 av Leibniz International Proceedings in Informatics (LIPIcs), side 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 og Avisay Tal. "Eksponentiell separasjon mellom grunne kvantekretser og ubegrensede fan-in grunne klassiske kretser". I Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. Side 515–526. STOC 2019New York, NY, USA (2019). Foreningen for datamaskiner.
https: / / doi.org/ 10.1145 / 3313276.3316404
[47] Natalie Parham. "Om kraften og begrensningene til grunne kvantekretser". Masteroppgave. University of Waterloo. (2022). url: https:///uwspace.uwaterloo.ca/handle/10012/18702.
https:///uwspace.uwaterloo.ca/handle/10012/18702
[48] Dmitri Maslov, Jin-Sung Kim, Sergey Bravyi, Theodore J Yoder og Sarah Sheldon. "Kvantefordel for beregninger med begrenset plass". Nature Physics 17, 894–897 (2021).
https://doi.org/10.1038/s41567-021-01271-7
[49] Farid Ablayev, Aida Gainutdinova, Marek Karpinski, Cristopher Moore og Christopher Pollett. "Om beregningskraften til sannsynlighets- og kvanteforgreningsprogram". Informasjon og beregning 203, 145–162 (2005).
https: / / doi.org/ 10.1016 / j.ic.2005.04.003
[50] D Shepherd og MJ Bremner. "Tidsmessig ustrukturert kvanteberegning". 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 og Anton Zeilinger. "Going Beyond Bell's Theorem". I Menas Kafatos, redaktør, Bell's Teorem, Quantum Theory and Conceptions of the Universe. Side 69–72. Dordrecht (1989). Springer Nederland.
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 og Clément Javerzac-Galy. "Effektive kvantealgoritmer for GHZ- og W-stater, og implementering på IBM Quantum Computer". Advanced Quantum Technologies 2, 1900015 (2019).
https: / / doi.org/ 10.1002 / qute.201900015
[53] RF Werner og MM Wolf. "All-multipartite klokke-korrelasjonsulikheter for to dikotomiske observerbare per sted". Phys. Rev. A 64, 032112 (2001).
https: / / doi.org/ 10.1103 / PhysRevA.64.032112
[54] Ryan O'Donnell. "Analyse av boolske funksjoner". 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 og Vladimir V. Podolskii. "Parity Decision Tree Complexity is Greater Than Granularity" (2018). arXiv:1810.08668.
arxiv: 1810.08668
[56] A Canteaut og M Videau. "Symmetriske boolske funksjoner". IEEE Transactions on Information Theory 51, 2791–2811 (2005).
https: / / doi.org/ 10.1109 / TIT.2005.851743
[57] Larry J Stockmeyer. "Om kombinasjonskompleksiteten til visse symmetriske boolske funksjoner". Matematisk systemteori 10, 323–336 (1976).
https: / / doi.org/ 10.1007 / BF01683282
[58] RF Arnold og MA Harrison. "Algebraiske egenskaper for symmetriske og delvis symmetriske boolske funksjoner". IEEE-transaksjoner på elektroniske datamaskiner EC-12, 244–251 (1963).
https:///doi.org/10.1109/PGEC.1963.263535
[59] An Braeken og Bart Preneel. "Om den algebraiske immuniteten til symmetriske boolske funksjoner". I Subhamoy Maitra, CE Veni Madhavan, og Ramarathnam Venkatesan, redaktører, Progress in Cryptology – INDOCRYPT 2005. Volum 3797 av Lecture Notes in Computer Science, side 35–48. Berlin, Heidelberg (2005). Springer Berlin Heidelberg.
https: / / doi.org/ 10.1007 / 11596219_4
[60] Harry Buhrman og Ronald de Wolf. "Kompleksitetstiltak og beslutningstrekompleksitet: en undersøkelse". Teoretisk informatikk 288, 21–43 (2002).
https://doi.org/10.1016/S0304-3975(01)00144-X
[61] Matthew Amy, Dmitri Maslov, Michele Mosca og Martin Roetteler. "En møte-i-midt-algoritme for rask syntese av dybdeoptimale kvantekretser". 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 og IL Markov. "Syntese av kvantelogiske kretser". 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 og Martti M Salomaa. "Effektiv dekomponering av kvanteporter". Phys. Rev. Lett. 92, 177902 (2004).
https: / / doi.org/ 10.1103 / PhysRevLett.92.177902
[64] Bei Zeng, Xie Chen og Isaac L Chuang. "Semi-Clifford-operasjoner, struktur av $mathcal{C}_{k}$-hierarki og portkompleksitet for feiltolerant kvanteberegning". Phys. Rev. A 77, 042313 (2008).
https: / / doi.org/ 10.1103 / PhysRevA.77.042313
[65] Gary J Mooney, Charles D Hill og Lloyd CL Hollenberg. "Kostnadsoptimal enkelt-qubit-portsyntese i Clifford-hierarkiet". Quantum 5, 396 (2021).
https://doi.org/10.22331/q-2021-02-15-396
[66] Nadish de Silva. "Effektiv kvanteportteleportering i høyere dimensjoner". Proceedings of the Royal Society A 477, 20200865 (2021).
https: / / doi.org/ 10.1098 / rspa.2020.0865
[67] Daniel Gottesman og Isaac L Chuang. "Demonstrere levedyktigheten til universell kvanteberegning ved bruk av teleportering og enkelt-qubit-operasjoner". Nature 402, 390–393 (1999).
https: / / doi.org/ 10.1038 / 46503
[68] Daniel Gottesman. "Heisenberg-representasjonen av kvantedatamaskiner" (1998). arXiv:quant-ph/9807006.
arxiv: Quant-ph / 9807006
[69] Vadym Kliuchnikov, Dmitri Maslov og Michele Mosca. "Rask og effektiv eksakt syntese av enkelt-qubit-enheter generert av clifford og t-porter". Kvanteinformasjon. 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 og Tamás Vértesi. "Test strukturen til flerpartssammenfiltring med klokkeulikheter". Phys. Rev. Lett. 108, 110501 (2012).
https: / / doi.org/ 10.1103 / PhysRevLett.108.110501
[71] Julia Kempe, Hirotada Kobayashi, Keiji Matsumoto, Ben Toner og Thomas Vidick. "Entangled Games er vanskelig å tilnærme". SIAM Journal on Computing 40, 848–877 (2011).
https: / / doi.org/ 10.1137 / 090751293
[72] Yihui Quek, Eneet Kaur og Mark M. Wilde. "Multivariat sporestimering i konstant kvantedybde". Quantum 8, 1220 (2024).
https://doi.org/10.22331/q-2024-01-10-1220
[73] Peter Selinger. "Effektiv Clifford+T-tilnærming av enkelt-Qubit-operatører". Kvanteinformasjon. Comput. 15, 159–180 (2015).
[74] Vadym Kliuchnikov, Dmitri Maslov og Michele Mosca. "Praktisk tilnærming av enkelt-Qubit-enheter av Single-Qubit Quantum Clifford og T-kretser". IEEE-transaksjoner på datamaskiner 65, 161–172 (2016).
https: / / doi.org/ 10.1109 / TC.2015.2409842
[75] Neil J Ross. "Optimal ancilla-fri CLIFFORD+V tilnærming av Z-rotasjoner". Kvanteinformasjon. 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 og Umesh Vazirani. "Kvantekompleksitetsteori". I Proceedings of the Twenty-Femth Annual ACM Symposium on Theory of Computing. Side 11–20. STOC '93New York, NY, USA (1993). Foreningen for datamaskiner.
https: / / doi.org/ 10.1145 / 167088.167097
[77] Alex Bocharov, Martin Roetteler og Krysta M Svore. "Effektiv syntese av sannsynlige kvantekretser med fallback". Phys. Rev. A 91, 052317 (2015).
https: / / doi.org/ 10.1103 / PhysRevA.91.052317
[78] Alex Bocharov, Martin Roetteler og Krysta M Svore. "Effektiv syntese av universelle gjentakende-inntil-suksess kvantekretser". Phys. Rev. Lett. 114, 080502 (2015).
https: / / doi.org/ 10.1103 / PhysRevLett.114.080502
[79] Ingo Wegener. "Kompleksiteten til boolske funksjoner". John Wiley $&$ Sons, Inc. USA (1987).
[80] Heribert Vollmer. "Introduksjon til kretskompleksitet: En enhetlig tilnærming". Springer Publishing Company, Incorporated. (2010). 1. utgave. 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. "Algebraiske metoder i teorien om nedre grenser for boolsk kretskompleksitet". I Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing. Side 77–82. STOC '87New York, NY, USA (1987). Foreningen for datamaskiner.
https: / / doi.org/ 10.1145 / 28395.28404
[82] Jaikumar Radhakrishnan. "Bedre grenser for terskelformler". I [1991] Proceedings 32nd Annual Symposium of Foundations of Computer Science. Side 314–323. IEEE Computer Society (1991).
https: / / doi.org/ 10.1109 / SFCS.1991.185384
[83] Michael J Fischer, Albert R Meyer og Michael S Paterson. "$Omega(Nlog n)$ Nedre grenser for lengden på boolske formler". SIAM J. Comput. 11, 416-427 (1982).
https: / / doi.org/ 10.1137 / 0211033
[84] Sanjeev Arora og Boaz Barak. "Beregningskompleksitet: En moderne tilnærming". Cambridge University Press. USA (2009). 1. utgave. url: https:///dl.acm.org/doi/abs/10.5555/1540612.
https: / / dl.acm.org/ doi / abs / 10.5555 / 1540612
[85] Scott Aaronson. "Hvor mye struktur trengs for store kvantehastigheter?" (2022). arXiv:2209.06930.
arxiv: 2209.06930
[86] David A Barrington. "Forgreningsprogrammer med avgrenset bredde i polynomstørrelse gjenkjenner nøyaktig de språkene 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 og Alex Arkhipov. "Den beregningsmessige kompleksiteten til lineær optikk". I Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing. Side 333–342. STOC '11New York, NY, USA (2011). Foreningen for datamaskiner.
https: / / doi.org/ 10.1145 / 1993636.1993682
[88] Peter W Shor. "Polynom-tidsalgoritmer for primfaktorisering og diskrete logaritmer på en kvantedatamaskin". SIAM Review 41, 303–332 (1999).
https: / / doi.org/ 10.1137 / S0036144598347011
[89] Daniel R Simon. "Om kraften til kvanteberegning". 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 og Unger Falk. "Begrensning for ikke-lokalitet i enhver verden der kommunikasjonskompleksiteten ikke er triviell". Phys. Rev. Lett. 96, 250401 (2006).
https: / / doi.org/ 10.1103 / PhysRevLett.96.250401
[91] Wim van Dam. "Usannsynlige konsekvenser av supersterk ikke-lokalitet". Natural Computing 12, 9–12 (2013).
https://doi.org/10.1007/s11047-012-9353-6
[92] Matthew Amy og Michele Mosca. "T-Count-optimalisering og 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 og Mohammad A Shokrollahi. "Algebraisk kompleksitetsteori". Bind 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 og Isaac L. Chuang. "Optimal Hamiltonsk simulering ved kvantesignalbehandling". Phys. Rev. Lett. 118, 010501 (2017).
https: / / doi.org/ 10.1103 / PhysRevLett.118.010501
[95] Jeongwan Haah. "Produktdekomponering av periodiske funksjoner i kvantesignalbehandling". Quantum 3, 190 (2019).
https://doi.org/10.22331/q-2019-10-07-190
[96] Scott Aaronson, Shalev Ben-David, Robin Kothari, Shravas Rao og Avisay Tal. "Grad vs. omtrentlig grad og kvanteimplikasjoner av Huangs sensitivitetsteorem". I Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. Side 1330–1342. STOC 2021New York, NY, USA (2021). Foreningen for datamaskiner.
https: / / doi.org/ 10.1145 / 3406325.3451047
[97] Hao Huang. "Induserte subgrafer av hyperkuber og et bevis på sensitivitetsformodningen". 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 og Juris Smotrovs. "Separasjoner i spørringskompleksitet basert på pekerfunksjoner". J. ACM 64 (2017).
https: / / doi.org/ 10.1145 / 3106234
[99] Peter Høyer og Robert Špalek. "Kvantekretser med ubegrenset fan-out". I Helmut Alt og Michel Habib, redaktører, STACS 2003. Side 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 og Akimasa Miyake. "Kvanteberegningsfordel attestert av ikke-lokale spill med den sykliske klyngetilstanden". Phys. Rev. Forskning 4, 033068 (2022).
https: / / doi.org/ 10.1103 / PhysRevResearch.4.033068
[101] Paul Herringer og Robert Raussendorf. "Klassifisering av målebasert kvantetråd i stabilisator PEPS". Quantum 7, 1041 (2023).
https://doi.org/10.22331/q-2023-06-12-1041
[102] Abhishek Anand. "Om kraften til sammenflettede kvante- og klassiske kretsløp med lav dybde". Masteroppgave. University of Waterloo. (2022). url: https:///uwspace.uwaterloo.ca/handle/10012/18805.
https:///uwspace.uwaterloo.ca/handle/10012/18805
[103] John Preskill. "Quantum Computing i NISQ-æraen og utover". Quantum 2, 79 (2018).
https://doi.org/10.22331/q-2018-08-06-79
[104] Bülent Demirel, Weikai Weng, Christopher Thalacker, Matty Hoban og Stefanie Barz. "Korrelasjoner for beregning og beregning for korrelasjoner". npj Quantum Information 7, 1–8 (2021).
https://doi.org/10.1038/s41534-020-00354-2
[105] Manoranjan Swain, Amit Rai, Bikash K Behera og Prasanta K Panigrahi. "Eksperimentell demonstrasjon av brudd på Mermins og Svetlichnys ulikheter for W- og 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 og Hidefumi Hiraishi. "Test skalerbare klokkeulikheter for kvantegraftilstander på ibm kvanteenheter". 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 og A. Acín. "Skalerbare klokkeulikheter for qubit-graftilstander og robust selvtesting". 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 og Sarah Sheldon. "Verifisering av multipartite sammenfiltrede Greenberger-Horne-Zeilinger-tilstander via flere kvantekoherenser". 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 og Ching-Ray Chang. "Mermins ulikheter av flere qubits med ortogonale målinger på IBM Q 53-qubit-system". Quantum Engineering 2, e45 (2020).
https:///doi.org/10.1002/que2.45
[110] Meron Sheffer, Daniel Azses og Emanuele G Dalla Torre. "Spille ikke-lokale Quantum-spill med seks støyende Qubits på skyen". Advanced Quantum Technologies 5, 2100081 (2022).
https: / / doi.org/ 10.1002 / qute.202100081
[111] Vedran Dunjko, Theodoros Kapourniotis og Elham Kashefi. "Quante-Enhanced Secure Delegated Classical Computing". Kvanteinformasjon. Comput. 16, 61–86 (2016).
[112] Stefanie Barz, Vedran Dunjko, Florian Schlederer, Merritt Moore, Elham Kashefi og Ian A. Walmsley. "Forbedret delegert databehandling ved bruk av sammenheng". 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 og Stefanie Barz. "Klassisk flerpartsberegning ved bruk av kvanteressurser". Physical Review A 96, 062317 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.96.062317
[114] Nasir Ahmed og Kamisetty Ramamohan Rao. "Walsh-hadamard transformasjon". I ortogonale transformasjoner for digital signalbehandling. Side 99–152. Springer (1975).
[115] Michael A Nielsen og Isaac L Chuang. "Kvanteberegning og kvanteinformasjon: 10th Anniversary Edition". Cambridge University Press. (2010).
https: / / doi.org/ 10.1017 / CBO9780511976667
[116] Philip Feinsilver og Jerzy Kocik. "Krawtchouk-polynomer og krawtchouk-matriser". Side 115–141. Nylige fremskritt i anvendt sannsynlighet. Springer USA. Boston, MA (2005).
https://doi.org/10.1007/0-387-23394-6_5
[117] Philip Feinsilver og Rene Schott. "Krawtchouk transformerer og viklinger". Bulletin of Mathematical SciencesPages 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 og IA Walmsley. "Kvanteinterferens muliggjør konstant-tid kvanteinformasjonsbehandling". Science Advances 5, eaau9674 (2019).
https: / / doi.org/ 10.1126 / sciadv.aau9674
[119] Ravindran Kannan og Achim Bachem. "Polynomiske algoritmer for å beregne Smith og Hermite normale former for en heltallsmatrise". SIAM Journal on Computing 8, 499–507 (1979).
https: / / doi.org/ 10.1137 / 0208040
[120] Josh Alman og Virginia Vassilevska Williams. "En raffinert lasermetode og raskere matrisemultiplikasjon". I forhandlingene av det trettiandre årlige ACM-SIAM-symposiet om diskrete algoritmer. Side 522–539. SODA '21USA (2021). Selskap for industriell og anvendt matematikk.
https: / / doi.org/ 10.1137 / 1.9781611976465.32
Sitert av
Denne artikkelen er utgitt i Quantum under Creative Commons Attribution 4.0 International (CC BY 4.0) tillatelse. Opphavsrett forblir hos de opprinnelige rettighetshaverne som forfatterne eller institusjonene deres.
- SEO-drevet innhold og PR-distribusjon. Bli forsterket i dag.
- PlatoData.Network Vertical Generative Ai. Styrk deg selv. Tilgang her.
- PlatoAiStream. Web3 Intelligence. Kunnskap forsterket. Tilgang her.
- PlatoESG. Karbon, CleanTech, Energi, Miljø, Solenergi, Avfallshåndtering. Tilgang her.
- PlatoHelse. Bioteknologisk og klinisk etterretning. Tilgang her.
- kilde: https://quantum-journal.org/papers/q-2024-04-09-1312/
