Quantum Advantage i Temporally Flat Measurement-baseret kvanteberegning

Genudgivet af Platon

Abonnenter: 0

Michael de Oliveira^1,2,3, Luís S. Barbosa^1,2,3, og Ernesto F. Galvão^3,4

¹University of Minho, Department of Computer Science, Braga, Portugal
²INESC TEC, Braga, Portugal
³International Iberian Nanotechnology Laboratory (INL) Av. Mestre Jose Veiga, 4715-330, Braga, Portugal
⁴Instituto de Física, Universidade Federal Fluminense Av. Gal. Milton Tavares de Souza s/n, Niterói, RJ, 24210-340, Brasilien

Finder du denne artikel interessant eller vil du diskutere? Scite eller efterlade en kommentar på SciRate.

Abstrakt

Flere klasser af kvantekredsløb har vist sig at give en kvanteberegningsfordel under visse antagelser. Studiet af stadig mere begrænsede klasser af kvantekredsløb, der er i stand til kvantefordele, er motiveret af mulige forenklinger i eksperimentelle demonstrationer. I dette papir studerer vi effektiviteten af målebaseret kvanteberegning med en fuldstændig flad tidsmæssig rækkefølge af målinger. Vi foreslår nye konstruktioner til deterministisk beregning af arbitrære boolske funktioner, der trækker på korrelationer, der er til stede i multi-qubit Greenberger, Horne og Zeilinger (GHZ) tilstande. Vi karakteriserer den nødvendige målekompleksitet ved hjælp af Clifford-hierarkiet og reducerer også generelt antallet af nødvendige qubits i forhold til tidligere konstruktioner. Især identificerer vi en familie af boolske funktioner, for hvilke deterministisk evaluering ved hjælp af ikke-adaptiv MBQC er mulig, med kvantefordel i bredde og antal porte i forhold til klassiske kredsløb.

Kvantefordel i tidsmæssigt flad måling baseret kvanteberegning PlatoBlockchain Data Intelligence. Lodret søgning. Ai.

Udvalgt billede: Den ikke-adaptive MBQC-model kan beskrives af en specifik beregningsarkitektur, der er opdelt i kvantetilstandsforberedelsesprocessen, målerutinen og den tilhørende præ- og postklassiske lineære behandling (øverst til venstre). Denne model letter studiet af ressourcekrav til evaluering af symmetriske boolske funktioner i form af det asymptotiske antal qubits og operationer, der kræves (øverst til højre). Disse elementer afslører vores hovedresultater [nederst], som er artikuleret for klassiske standard- og kvanteportsæt og kredsløbsbeskrivelser [nederst til venstre], der karakteriserer sættet af boolske funktioner, der demonstrerer kvantefordele med hensyn til antallet af porte og bredden af kredsløb (nederst til højre).

[Indlejret indhold]

Populært resumé

Quantum computing lover at levere beregningsfordele med hensyn til de bedste klassiske algoritmer til mange opgaver. Strenge resultater, der kvantificerer denne fordel, er sjældne, og hjælper med at fokusere forskningen på de afgørende kvanteressourcer, der leverer bedre end klassisk ydeevne. Denne kvantefordel kan ske med hensyn til forskellige ressourcer: det samlede antal nødvendige porte, dybden af de resulterende kredsløb eller størrelsen af den anvendte hukommelse (kendt som kredsløbsbredde).

I dette arbejde analyserer vi evalueringen af boolske funktioner, noget som kvantecomputere kan gøre ved at bruge de korrelerede resultater af målinger på sammenfiltrede Greenberger-Horne-Zeilinger (GHZ) tilstande af mange qubits. Denne variant af målebaseret kvanteberegning kræver ingen adaptivitet, så alle qubits kan måles samtidigt. Denne flade tidsmæssige struktur af beregningsprocessen resulterer i nogle tilfælde i meget økonomiske kvantekredsløb. Vi identificerer egenskaberne for en boolsk funktion, der bestemmer, hvor mange qubits der er nødvendige, og den nødvendige målingspræcision. For en bestemt familie af boolske funktioner viser vi, at der er en streng fordel i bredden og antallet af porte i forhold til den tilsvarende familie af klassiske kredsløb. I fremtiden kan vores teknikker hjælpe med at udtænke bedre måder at bruge kvanteressourcer på også til adaptive kredsløb, der viser mere beregningsmæssig udtryksevne.

► BibTeX-data

@article{Oliveira2024quantumadvantagein, doi = {10.22331/q-2024-04-09-1312}, url = {https://doi.org/10.22331/q-2024-04-09-1312}, titel = {Kvantefordel i tidsmæssigt flad måling-baseret kvanteberegning}, forfatter = {Oliveira, Michael de og Barbosa, Lu{'{i}}s S. og Galv{~{a}}o, Ernesto F.}, journal = {{Quantum}}, issn = {2521-327X}, udgiver = {{Verein zur F{“{o}}rderung des Open Access Publizierens in the Quantenwissenschaften}}, volumen = {8}, sider = {1312}, måned = apr, år = {2024} }

► Referencer

[1] Scott Aaronson, DeVon Ingram og William Kretschmer. "BQP's akrobatik". I Shachar Lovett, redaktør, 37. Computational Complexity Conference (CCC 2022). Bind 234 af 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 kvanteberegningshastigheden". Proceedings fra Royal Society of London. Serie A: Matematisk, fysisk og ingeniørvidenskab 459, 2011–2032 (2003).
https:///doi.org/10.1098/rspa.2002.1097

[3] Mark Howard, Joel Wallman, Victor Veitch og Joseph Emerson. "Kontekstualitet giver 'magien' til 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 ressource til 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-funktioner og kvanteberegningshastighed". Phys. Rev. A 71, 042302 (2005).
https:///doi.org/10.1103/PhysRevA.71.042302

[6] A. Mari og J. Eisert. "Positive wigner-funktioner gør klassisk simulering af kvanteberegning effektiv". Phys. Rev. Lett. 109, 230503 (2012).
https:///doi.org/10.1103/PhysRevLett.109.230503

[7] Kærlighed K. Grover. "Fordelene ved superposition". Science 280, 228-228 (1998).
https://doi.org/10.1126/science.280.5361.228

[8] Robert Raussendorf og Hans J. Briegel. "En envejs kvantecomputer". 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 ressourcer til målebaseret kvanteberegning". Phys. Rev. Lett. 97, 150504 (2006).
https:///doi.org/10.1103/PhysRevLett.97.150504

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

[11] Vincent Danos og Elham Kashefi. "Determinisme i envejsmodellen". 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. "Generaliseret flow og determinisme i målebaseret 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. "Gennemsnitlig sagskompleksitet versus omtrentlig simulering af 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ålebaseret 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. "Opnåelse af kvanteoverherredømme med sparsomme og støjende 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 af mange-krops kvantesystemer". Quantum 5, 465 (2021).
https://doi.org/10.22331/q-2021-06-02-465

[17] Masahito Hayashi og Yuki Takeuchi. "Verificering af pendlingskvanteberegninger via troskabsestimat af vægtede graftilstande". 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 til kvantesimulering, der viser en kvantehastighedsstigning". Phys. Rev. X 8, 021010 (2018).
https:///doi.org/10.1103/PhysRevX.8.021010

[19] Jacob Miller, Stephen Sanders og Akimasa Miyake. "Kvanteoverherredømme i konstant-tidsmåling-baseret beregning: En samlet arkitektur til prøveudtagning og verifikation". 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ålebaseret kvanteberegning og multiparts Bell-uligheder". New Journal of Physics 13, 23014 (2011).
https://doi.org/10.1088/1367-2630/13/2/023014

[21] Ryuhei Mori. "Periodisk Fourier-repræsentation af booleske funktioner". Kvante info. 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 af ressourcer til målebaseret 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. "Krften ved qutrits til ikke-adaptiv målebaseret 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. "Uligheder af klokketype til at opdage ægte $mathit{n}$-Krops-uadskillelighed". 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. "Klokke ikke-lokalitet". Rev. Mod. Phys. 86, 419-478 (2014).
https:///doi.org/10.1103/RevModPhys.86.419

[26] Dmitrijs Kravčenko. "Kvantespil, kvantestater, deres egenskaber og applikationer". Ph.d.-afhandling. Latvijas Universitāte. (2013).

[27] William Slofstra. "Nedre grænser for den sammenfiltring, der er nødvendig for at spille XOR ikke-lokale spil". 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 ved kvantestrategier i tilfældige symmetriske xor-spil". 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. "Beviselig fordel for kvantestrategier i tilfældige symmetriske XOR-spil". I Simone Severini og Fernando Brandao, redaktører, 8. konference om teorien om kvanteberegning, kommunikation og kryptografi (TQC 2013). Bind 22 af 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. "Konsekvenser af kommunikationskompleksitet 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. "Informationskausalitet som et fysisk princip". 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 sammenhænge som en informationsteoretisk ressource". Phys. Rev. A 71, 022101 (2005).
https:///doi.org/10.1103/PhysRevA.71.022101

[34] AA Razborov. "Kvantekommunikationskompleksitet af symmetriske prædikater". Izvestiya: Mathematics 67, 145 (2003).
https://doi.org/10.1070/IM2003v067n01ABEH000422

[35] Zhiqiang Zhang og Yaoyun Shi. "Kommunikationskompleksiteter af symmetriske 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. "Ikke-lokale bokse og kommunikationskompleksitet". Kandidatafhandling. 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 Søn. "Generaliserede ikke-lokalitetskriterier under korrelationssymmetrien". 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 ressource til målebaseret kvanteberegning ud over 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 lavvandede kredsløb". 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 giver en kvantefordel" (2022). arXiv:2209.14158.
arXiv: 2209.14158

[42] François Le Gall. "Gennemsnitlig kvantefordel med lavvandede kredsløb". I Amir Shpilka, redaktør, 34th Computational Complexity Conference (CCC 2019). Bind 137 af 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: certificerbar tilfældighed fra kredsløb med lav dybde". Kommunikation i matematisk fysik 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øjende lavvandede kredsløb". 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 lavvandede kredsløb under vilkårlig korruption". I Hee-Kap Ahn og Kunihiko Sadakane, redaktører, 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Bind 212 af 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. "Eksponentiel adskillelse mellem lavvandede kvantekredsløb og ubegrænsede fan-in lavvandede klassiske kredsløb". 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 begrænsningerne af lavvandede kvantekredsløb". Kandidatafhandling. 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 til beregninger med begrænset plads". 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 i probabilistisk og kvanteforgreningsprogram". Information and Computation 203, 145-162 (2005).
https:///doi.org/10.1016/j.ic.2005.04.003

[50] D Shepherd og MJ Bremner. "Tidsmæssigt ustruktureret 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. "Gå ud over Bells sætning". I Menas Kafatos, redaktør, Bell's Theorem, Quantum Theory and Conceptions of the Universe. Side 69-72. Dordrecht (1989). Springer Holland.
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 til GHZ- og W-stater og implementering på IBM-kvantecomputeren". Advanced Quantum Technologies 2, 1900015 (2019).
https:///doi.org/10.1002/qute.201900015

[53] RF Werner og MM Wolf. "All-multipartite klokke-korrelation uligheder for to dikotomiske observerbare pr. sted". Phys. Rev. A 64, 032112 (2001).
https:///doi.org/10.1103/PhysRevA.64.032112

[54] Ryan O'Donnell. "Analyse af booleske 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 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 booleske funktioner". IEEE Transactions on Information Theory 51, 2791–2811 (2005).
https:///doi.org/10.1109/TIT.2005.851743

[57] Larry J Stockmeyer. "Om den kombinationskompleksitet af visse symmetriske boolske funktioner". Matematisk systemteori 10, 323-336 (1976).
https:///doi.org/10.1007/BF01683282

[58] RF Arnold og MA Harrison. "Algebraiske egenskaber for symmetriske og delvist symmetriske booleske funktioner". IEEE-transaktioner på elektroniske computere EC-12, 244-251 (1963).
https://doi.org/10.1109/PGEC.1963.263535

[59] An Braeken og Bart Preneel. "Om den algebraiske immunitet af symmetriske booleske funktioner". I Subhamoy Maitra, CE Veni Madhavan, og Ramarathnam Venkatesan, redaktører, Progress in Cryptology – INDOCRYPT 2005. Bind 3797 af 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. "Kompleksitetsmål og beslutningstrækompleksitet: en undersøgelse". Teoretisk datalogi 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 Meet-in-the-Middle-algoritme til hurtig syntese af dybdeoptimale kvantekredsløb". 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 af kvantelogiske kredsløb". 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 nedbrydning af kvanteporte". 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 operationer, struktur af $mathcal{C}_{k}$ hierarki og gatekompleksitet til fejltolerant 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. "Omkostningsoptimal single-qubit-gatesyntese i Clifford-hierarkiet". Quantum 5, 396 (2021).
https://doi.org/10.22331/q-2021-02-15-396

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

[67] Daniel Gottesman og Isaac L Chuang. "Demonstrer levedygtigheden af universel kvanteberegning ved hjælp af teleportering og enkelt-qubit-operationer". Nature 402, 390-393 (1999).
https:///doi.org/10.1038/46503

[68] Daniel Gottesman. "Heisenberg-repræsentationen af kvantecomputere" (1998). arXiv:quant-ph/9807006.
arXiv:quant-ph/9807006

[69] Vadym Kliuchnikov, Dmitri Maslov og Michele Mosca. "Hurtig og effektiv nøjagtig syntese af single-qubit unitaries genereret af clifford og t gates". Kvante info. 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 af flerpartssammenfiltring med klokkeuligheder". 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 svære at 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ærmelse af enkelt-Qubit-operatører". Kvante info. Comput. 15, 159-180 (2015).

[74] Vadym Kliuchnikov, Dmitri Maslov og Michele Mosca. "Praktisk tilnærmelse af enkelt-Qubit-enheder ved Single-Qubit Quantum Clifford og T-kredsløb". IEEE-transaktioner på computere 65, 161-172 (2016).
https:///doi.org/10.1109/TC.2015.2409842

[75] Neil J Ross. "Optimal ancilla-fri CLIFFORD+V approksimation af Z-rotationer". Kvante info. 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 11th Annual ACM Symposium on Theory of Computing. Side 20-93. STOC '1993New York, NY, USA (XNUMX). Foreningen for Datamaskiner.
https:///doi.org/10.1145/167088.167097

[77] Alex Bocharov, Martin Roetteler og Krysta M Svore. "Effektiv syntese af probabilistiske kvantekredsløb 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 af universelle gentagelses-indtil-succes kvantekredsløb". Phys. Rev. Lett. 114, 080502 (2015).
https:///doi.org/10.1103/PhysRevLett.114.080502

[79] Ingo Wegener. "Kompleksiteten af booleske funktioner". John Wiley $&$ Sons, Inc. USA (1987).

[80] Heribert Vollmer. "Introduktion til kredsløbskompleksitet: En ensartet tilgang". Springer Publishing Company, Incorporated. (2010). 1. udgave. 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 grænser for boolsk kredsløbskompleksitet". 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 grænser for tærskelformler". 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 grænser for længden af booleske formler". SIAM J. Comput. 11, 416-427 (1982).
https:///doi.org/10.1137/0211033

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

[85] Scott Aaronson. "Hvor meget struktur er der brug for til enorme kvantehastigheder?" (2022). arXiv:2209.06930.
arXiv: 2209.06930

[86] David A Barrington. "Afgrænsningsprogrammer i polynomisk størrelse genkender præcis de sprog 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 beregningsmæssige kompleksitet af lineær optik". I Proceedings of the 333. årlige ACM Symposium on Theory of Computing. Side 342–11. STOC '2011New York, NY, USA (XNUMX). Foreningen for Datamaskiner.
https:///doi.org/10.1145/1993636.1993682

[88] Peter W Shor. "Polynomiale-tidsalgoritmer til primfaktorisering og diskrete logaritmer på en kvantecomputer". SIAM Review 41, 303-332 (1999).
https:///doi.org/10.1137/S0036144598347011

[89] Daniel R Simon. "Om kraften ved 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. "Grænse for ikke-lokalitet i enhver verden, hvor kommunikationskompleksitet ikke er triviel". Phys. Rev. Lett. 96, 250401 (2006).
https:///doi.org/10.1103/PhysRevLett.96.250401

[91] Wim van Dam. "Utrolige konsekvenser af superstærk 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-optimering 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 Hamilton-simulering ved kvantesignalbehandling". Phys. Rev. Lett. 118, 010501 (2017).
https:///doi.org/10.1103/PhysRevLett.118.010501

[95] Jeongwan Haah. "Produktnedbrydning af periodiske funktioner 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. "Grader vs. omtrentlige grader og kvanteimplikationer af Huangs følsomhedsteorem". 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. "Inducerede subgrafer af hyperkuber og et bevis på følsomhedsformodningen". 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. "Separationer i forespørgselskompleksitet baseret på markørfunktioner". J. ACM 64 (2017).
https:///doi.org/10.1145/3106234

[99] Peter Høyer og Robert Špalek. "Kvantekredsløb med ubegrænset 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 attesteret af ikke-lokale spil med den cykliske klyngetilstand". Phys. Rev. Research 4, 033068 (2022).
https:///doi.org/10.1103/PhysRevResearch.4.033068

[101] Paul Herringer og Robert Raussendorf. "Klassificering af målebaseret kvantetråd i stabilisator PEPS". Quantum 7, 1041 (2023).
https://doi.org/10.22331/q-2023-06-12-1041

[102] Abhishek Anand. "Om kraften i sammenflettede kvantekredsløb med lav dybde og klassiske kredsløb". Kandidatafhandling. 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 derefter". 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. "Korrelationer til beregning og beregning for 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 og Prasanta K Panigrahi. "Eksperimentel demonstration af krænkelserne af Mermins og Svetlichnys uligheder 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 klokkeuligheder for kvantegraftilstande på ibm kvanteenheder". 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 klokkeuligheder for qubit-graftilstande og robust selvtest". 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. "Verifikation af multipartite sammenfiltrede Greenberger-Horne-Zeilinger-tilstande via flere kvantekohærenser". 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 uligheder af 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. "At spille Quantum Nonlocal-spil med seks støjende Qubits på skyen". Advanced Quantum Technologies 5, 2100081 (2022).
https:///doi.org/10.1002/qute.202100081

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

[112] Stefanie Barz, Vedran Dunjko, Florian Schlederer, Merritt Moore, Elham Kashefi og Ian A. Walmsley. "Forbedret delegeret databehandling ved hjælp af sammenhæng". 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 hjælp af kvanteressourcer". Fysisk anmeldelse A 96, 062317 (2017).
https:///doi.org/10.1103/PhysRevA.96.062317

[114] Nasir Ahmed og Kamisetty Ramamohan Rao. "Walsh-hadamard transformation". I Ortogonale transformationer til digital signalbehandling. Side 99-152. Springer (1975).

[115] Michael A Nielsen og Isaac L Chuang. "Kvanteberegning og kvanteinformation: 10th Anniversary Edition". Cambridge University Press. (2010).
https:///doi.org/10.1017/CBO9780511976667

[116] Philip Feinsilver og Jerzy Kocik. "Krawtchouk-polynomier og krawtchouk-matricer". Side 115-141. Seneste fremskridt i anvendt sandsynlighed. 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 Sciences Side 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 muliggør konstant-tids kvanteinformationsbehandling". Science Advances 5, eaau9674 (2019).
https:///doi.org/10.1126/sciadv.aau9674

[119] Ravindran Kannan og Achim Bachem. "Polynomiale algoritmer til beregning af Smiths og Hermites normale former for en heltalsmatrix". SIAM Journal on Computing 8, 499–507 (1979).
https:///doi.org/10.1137/0208040

[120] Josh Alman og Virginia Vassilevska Williams. "En raffineret lasermetode og hurtigere matrixmultiplikation". I forbindelse med det 522. årlige ACM-SIAM-symposium om diskrete algoritmer. Side 539–21. SODA '2021USA (XNUMX). Selskab for Industriel og Anvendt Matematik.
https:///doi.org/10.1137/1.9781611976465.32

Citeret af

Dette papir er udgivet i Quantum under Creative Commons Attribution 4.0 International (CC BY 4.0) licens. Ophavsretten forbliver hos de originale copyright-indehavere, såsom forfatterne eller deres institutioner.