Avantaj cuantic în calculul cuantic bazat pe măsurare temporal

Avantaj cuantic în calculul cuantic bazat pe măsurare temporal

Marca temporală: 9 aprilie 2024 7:15

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

1Universitatea din Minho, Departamentul de Informatică, Braga, Portugalia
2INESC TEC, Braga, Portugalia
3Laboratorul Internațional Iberic de Nanotehnologie (INL) Av. Mestre Jose Veiga, 4715-330, Braga, Portugalia
4Instituto de Física, Universitatea Federal Fluminense Av. Fată. Milton Tavares de Souza s/n, Niterói, RJ, 24210-340, Brazilia

Găsiți această lucrare interesant sau doriți să discutați? Scite sau lasă un comentariu la SciRate.

Abstract

S-a demonstrat că mai multe clase de circuite cuantice oferă un avantaj computațional cuantic în anumite ipoteze. Studiul claselor tot mai restrânse de circuite cuantice capabile de avantaj cuantic este motivat de posibile simplificări în demonstrațiile experimentale. În această lucrare studiem eficiența calculului cuantic bazat pe măsurători cu o ordonare temporală complet plată a măsurătorilor. Propunem noi construcții pentru calculul determinist al funcțiilor booleene arbitrare, bazându-ne pe corelații prezente în stările Greenberger, Horne și Zeilinger (GHZ) multi-qubit. Caracterizăm complexitatea necesară de măsurare folosind ierarhia Clifford și, în general, reducem numărul de qubiți necesari față de construcțiile anterioare. În special, identificăm o familie de funcții booleene pentru care este posibilă evaluarea deterministă folosind MBQC neadaptativ, prezentând avantaj cuantic în lățime și număr de porți în raport cu circuitele clasice.

Avantaj cuantic în calculul cuantic bazat pe măsurare temporal plată PlatoBlockchain Data Intelligence. Căutare verticală. Ai.

Imagine prezentată: Modelul MBQC neadaptativ poate fi descris printr-o arhitectură de calcul specifică care este împărțită în procesul de pregătire a stării cuantice, rutina de măsurare și procesarea liniară pre și post-clasică asociată (stânga sus). Acest model facilitează studiul cerințelor de resurse pentru evaluarea funcțiilor booleene simetrice în ceea ce privește numărul asimptotic de qubiți și operațiile necesare (dreapta sus). Aceste elemente dezvăluie principalele noastre rezultate [jos], care sunt articulate pentru seturi standard de porți clasice și cuantice și descrieri de circuite [jos, stânga], care caracterizează setul de funcții booleene care demonstrează avantajul cuantic în ceea ce privește numărul de porți și lățimea circuite (dreapta jos).

[Conținutul încorporat]

Rezumat popular

Calculul cuantic promite să ofere un avantaj computațional în ceea ce privește cei mai buni algoritmi clasici pentru multe sarcini. Rezultatele riguroase care cuantifică acest avantaj sunt rare și ajută la concentrarea cercetării asupra resurselor cuantice cruciale care oferă performanțe mai bune decât cele clasice. Acest avantaj cuantic se poate întâmpla în raport cu diferite resurse: numărul total de porți necesare, adâncimea circuitelor rezultate sau dimensiunea memoriei utilizate (cunoscută ca lățimea circuitului).

În această lucrare analizăm evaluarea funcțiilor booleene, lucru pe care computerele cuantice îl pot face folosind rezultatele corelate ale măsurătorilor pe stările încurcate Greenberger-Horne-Zeilinger (GHZ) ale multor qubiți. Această variantă de calcul cuantic bazat pe măsurare nu necesită adaptabilitate, astfel încât toți qubiții pot fi măsurați simultan. Această structură temporală plată a procesului de calcul are ca rezultat, în unele cazuri, circuite cuantice foarte economice. Identificăm caracteristicile unei funcții booleene care determină câți qubiți sunt necesari și precizia de măsurare necesară. Pentru o anumită familie de funcții booleene arătăm că există un avantaj riguros în lățimea și numărul de porți față de familia corespunzătoare de circuite clasice. În viitor, tehnicile noastre pot ajuta la conceperea unor modalități mai bune de utilizare a resurselor cuantice și pentru circuite adaptive care prezintă mai multă expresivitate computațională.

► Date BibTeX

► Referințe

[1] Scott Aaronson, DeVon Ingram și William Kretschmer. „Acrobația BQP”. În Shachar Lovett, editor, a 37-a Conferință de complexitate computațională (CCC 2022). Volumul 234 din Leibniz International Proceedings in Informatics (LIPIcs), paginile 20:1–20:17. Dagstuhl, Germania (2022). Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
https: / / doi.org/ 10.4230 / LIPIcs.CCC.2022.20

[2] Richard Jozsa și Noah Linden. „Despre rolul întanglementării în accelerarea cuantică-computațională”. Proceedings of the Royal Society of London. Seria A: Științe matematice, fizice și inginerie 459, 2011–2032 (2003).
https: / / doi.org/ 10.1098 / rspa.2002.1097

[3] Mark Howard, Joel Wallman, Victor Veitch și Joseph Emerson. „Contextualitatea furnizează „magia” calculului cuantic”. Nature 510, 351–355 (2014).
https: / / doi.org/ 10.1038 / nature13460

[4] Juan Bermejo-Vega, Nicolas Delfosse, Dan E. Browne, Cihan Okay și Robert Raussendorf. „Contextualitatea ca resursă pentru modele de calcul cuantic cu qubiți”. Fiz. Rev. Lett. 119, 120505 (2017).
https: / / doi.org/ 10.1103 / PhysRevLett.119.120505

[5] Ernesto F. Galvão. „Funcții wigner discrete și accelerare a calculului cuantic”. Fiz. Rev. A 71, 042302 (2005).
https: / / doi.org/ 10.1103 / PhysRevA.71.042302

[6] A. Mari şi J. Eisert. „Funcțiile wigner pozitive fac simularea clasică a calculului cuantic eficient”. Fiz. Rev. Lett. 109, 230503 (2012).
https: / / doi.org/ 10.1103 / PhysRevLett.109.230503

[7] Lov K. Grover. „Avantajele suprapunerii”. Science 280, 228–228 (1998).
https: / / doi.org/ 10.1126 / science.280.5361.228

[8] Robert Raussendorf și Hans J. Briegel. „Un computer cuantic unidirecțional”. Fiz. Rev. Lett. 86, 5188–5191 (2001).
https: / / doi.org/ 10.1103 / PhysRevLett.86.5188

[9] Maarten Van den Nest, Akimasa Miyake, Wolfgang Dür și Hans J. Briegel. „Resurse universale pentru calculul cuantic bazat pe măsurare”. Fiz. Rev. Lett. 97, 150504 (2006).
https: / / doi.org/ 10.1103 / PhysRevLett.97.150504

[10] Janet Anders și Dan E. Browne. „Puterea de calcul a corelațiilor”. Fiz. Rev. Lett. 102, 050502 (2009).
https: / / doi.org/ 10.1103 / PhysRevLett.102.050502

[11] Vincent Danos și Elham Kashefi. „Determinism în modelul unidirecțional”. Fiz. Rev. A 74, 052310 (2006).
https: / / doi.org/ 10.1103 / PhysRevA.74.052310

[12] Daniel E Browne, Elham Kashefi, Mehdi Mhalla și Simon Perdrix. „Flux generalizat și determinism în calculul cuantic bazat pe măsurare”. New Journal of Physics 9, 250 (2007).
https:/​/​doi.org/​10.1088/​1367-2630/​9/​8/​250

[13] Michael J Bremner, Ashley Montanaro și Dan J Shepherd. „Complexitatea medie a cazului versus simularea aproximativă a calculelor cuantice de navetă”. Fiz. 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 și Dan E. Browne. „Calcul clasic bazat pe măsurare”. Fiz. Rev. Lett. 112, 140505 (2014).
https: / / doi.org/ 10.1103 / PhysRevLett.112.140505

[15] Michael J. Bremner, Ashley Montanaro și Dan J. Shepherd. „Atingerea supremației cuantice cu calcule cuantice de navetă rare și zgomotoase”. Quantum 1, 8 (2017).
https:/​/​doi.org/​10.22331/​q-2017-04-25-8

[16] Leonardo Novo, Juani Bermejo-Vega și Raúl García-Patrón. „Avantaj cuantic din măsurătorile de energie ale sistemelor cuantice cu mai multe corpuri”. Quantum 5, 465 (2021).
https:/​/​doi.org/​10.22331/​q-2021-06-02-465

[17] Masahito Hayashi și Yuki Takeuchi. „Verificarea calculelor cuantice de navetă prin estimarea fidelității stărilor grafice ponderate”. 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 și Jens Eisert. „Arhitecturi pentru simularea cuantică care arată o accelerare cuantică”. Fiz. Rev. X 8, 021010 (2018).
https: / / doi.org/ 10.1103 / PhysRevX.8.021010

[19] Jacob Miller, Stephen Sanders și Akimasa Miyake. „Supremația cuantică în calculul bazat pe măsurare în timp constant: o arhitectură unificată pentru eșantionare și verificare”. Fiz. Rev. A 96, 062320 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.96.062320

[20] Matty J Hoban, Earl T Campbell, Klearchos Loukopoulos și Dan E Browne. „Calcul cuantic bazat pe măsurare neadaptativă și inegalitățile Bell multipartite”. New Journal of Physics 13, 23014 (2011).
https:/​/​doi.org/​10.1088/​1367-2630/​13/​2/​023014

[21] Ryuhei Mori. „Reprezentarea periodică Fourier a funcțiilor booleene”. Informații cuantice. Calculator. 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 și Stephen D Bartlett. „Ierarhii de resurse pentru calculul cuantic bazat pe măsurare”. New Journal of Physics 25, 013002 (2023).
https://​/​doi.org/​10.1088/​1367-2630/​acaee2

[23] Jelena Mackeprang, Daniel Bhatti, Matty J Hoban și Stefanie Barz. „Puterea qutriților pentru calculul cuantic bazat pe măsurare neadaptativă”. New Journal of Physics 25, 073007 (2023).
https://​/​doi.org/​10.1088/​1367-2630/​acdf77

[24] Daniel Collins, Nicolas Gisin, Sandu Popescu, David Roberts și Valerio Scarani. „Inegalități de tip clopot pentru a detecta adevărata $mathit{n}$-Inseparabilitatea corporală”. Fiz. Rev. Lett. 88, 170405 (2002).
https: / / doi.org/ 10.1103 / PhysRevLett.88.170405

[25] Nicolas Brunner, Daniel Cavalcanti, Stefano Pironio, Valerio Scarani și Stephanie Wehner. „Nelocalitatea clopoțelului”. Rev. Mod. Fiz. 86, 419–478 (2014).
https: / / doi.org/ 10.1103 / RevModPhys.86.419

[26] Dmitrijs Kravčenko. „Jocuri cuantice, state cuantice, proprietățile și aplicațiile lor”. Teză de doctorat. Universitatea din Latvijas. (2013).

[27] William Slofstra. „Limite inferioare ale încurcăturii necesare pentru a juca jocuri XOR non-locale”. Journal of Mathematical Physics 52, 102202 (2011).
https: / / doi.org/ 10.1063 / 1.3652924

[28] Andris Ambainis, Jānis Iraids, Dmitry Kravchenko și Madars Virza. „Avantajele strategiilor cuantice în jocurile aleatoare simetrice xor”. În Antonín Kučera, Thomas A. Henzinger, Jaroslav Nešetřil, Tomáš Vojnar și David Antoš, editori, Mathematical and Engineering Methods in Computer Science. Paginile 57–68. Berlin, Heidelberg (2013). Springer Berlin Heidelberg.
https:/​/​doi.org/​10.1007/​978-3-642-36046-6_7

[29] Andris Ambainis și Janis Iraids. „Avantaj dovedibil pentru strategiile cuantice în jocurile XOR simetrice aleatorii”. În Simone Severini și Fernando Brandao, editori, a 8-a Conferință privind teoria calculului cuantic, comunicării și criptografiei (TQC 2013). Volumul 22 din Leibniz International Proceedings in Informatics (LIPIcs), paginile 146–156. Dagstuhl, Germania (2013). Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
https: / / doi.org/ 10.4230 / LIPIcs.TQC.2013.146

[30] Samuel Marcovitch și Benni Reznik. „Implicații ale complexității comunicațiilor în sistemele multipartite”. Fiz. 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 și Marek Żukowski. „Cauzalitatea informației ca principiu fizic”. Nature 461, 1101–1104 (2009).
https: / / doi.org/ 10.1038 / nature08400

[32] Sandu Popescu și Daniel Rohrlich. „Nonlocalitatea cuantică ca 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 și David Roberts. „Corelațiile nonlocale ca resursă teoretică informațională”. Fiz. Rev. A 71, 022101 (2005).
https: / / doi.org/ 10.1103 / PhysRevA.71.022101

[34] AA Razborov. „Complexitatea comunicării cuantice a predicatelor simetrice”. Izvestiya: Matematică 67, 145 (2003).
https:/​/​doi.org/​10.1070/​IM2003v067n01ABEH000422

[35] Zhiqiang Zhang și Yaoyun Shi. „Complexități de comunicare ale funcțiilor XOR simetrice”. 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. „Cutiile non-locale și complexitatea comunicării”. Teza de masterat. Universitatea 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 și Wonmin Son. „Criterii generalizate de nonlocalitate sub simetria corelației”. Fiz. Rev. A 98, 022116 (2018).
https: / / doi.org/ 10.1103 / PhysRevA.98.022116

[38] Markus Frembs, Sam Roberts și Stephen D Bartlett. „Contextualitatea ca resursă pentru calculul cuantic bazat pe măsurare dincolo de qubiți”. New Journal of Physics 20, 103011 (2018).
https://​/​doi.org/​10.1088/​1367-2630/​aae3ad

[39] Sergey Bravyi, David Gosset și Robert König. „Avantaj cuantic cu circuite superficiale”. Science 362, 308–311 (2018).
https://​/​doi.org/​10.1126/​science.aar3106

[40] Daniel Grier și Luke Schaeffer. „Circuite interactive Clifford superficiale: Avantaj cuantic față de NC¹ și dincolo”. În Proceedings of the 52th Annual ACM SIGACT Symposium on Theory of Computing. Paginile 875–888. STOC 2020New York, NY, SUA (2020). Asociația pentru Mașini de Calcul.
https: / / doi.org/ 10.1145 / 3357713.3384332

[41] Libor Caha, Xavier Coiteux-Roy și Robert Koenig. „Teleportarea cu un singur qubit oferă un avantaj cuantic” (2022). arXiv:2209.14158.
arXiv: 2209.14158

[42] François Le Gall. „Avantajul cuantic al cazului mediu cu circuite superficiale”. În Amir Shpilka, editor, a 34-a Conferință de complexitate computațională (CCC 2019). Volumul 137 din Leibniz International Proceedings in Informatics (LIPIcs), paginile 21:1—-21:20. Dagstuhl, Germania (2019). Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
https: / / doi.org/ 10.4230 / LIPIcs.CCC.2019.21

[43] Matthew Coudron, Jalex Stark și Thomas Vidick. „Localitatea comercială pentru timp: aleatorie certificabilă din circuite cu adâncime mică”. Comunicații în fizica matematică 382, ​​49–86 (2021).
https: / / doi.org/ 10.1007 / s00220-021-03963-w

[44] Sergey Bravyi, David Gosset, Robert König și Marco Tomamichel. „Avantaj cuantic cu circuite superficiale zgomotoase”. Nature Physics 16, 1040–1045 (2020).
https: / / doi.org/ 10.1038 / s41567-020-0948-z

[45] Atsuya Hasegawa și François Le Gall. „Avantaj cuantic cu circuite superficiale sub corupție arbitrară”. În Hee-Kap Ahn și Kunihiko Sadakane, editori, al 32-lea Simpozion internațional privind algoritmi și calcul (ISAAC 2021). Volumul 212 din Leibniz International Proceedings in Informatics (LIPIcs), paginile 74:1–74:16. Dagstuhl, Germania (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 și Avishay Tal. „Separarea exponențială între circuitele cuantice superficiale și circuitele clasice superficiale nelimitate”. În Proceedings of the 51th Annual ACM SIGACT Symposium on Theory of Computing. Paginile 515–526. STOC 2019New York, NY, SUA (2019). Asociația pentru Mașini de Calcul.
https: / / doi.org/ 10.1145 / 3313276.3316404

[47] Natalie Parham. „Despre puterea și limitările circuitelor cuantice superficiale”. Teza de masterat. Universitatea din 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 și Sarah Sheldon. „Avantaj cuantic pentru calcule cu spațiu limitat”. Nature Physics 17, 894–897 (2021).
https:/​/​doi.org/​10.1038/​s41567-021-01271-7

[49] Farid Ablayev, Aida Gainutdinova, Marek Karpinski, Cristopher Moore și Christopher Pollett. „Despre puterea de calcul a programului de ramificare probabilistică și cuantică”. Information and Computation 203, 145–162 (2005).
https: / / doi.org/ 10.1016 / j.ic.2005.04.003

[50] D Shepherd și MJ Bremner. „Calcul cuantic nestructurat temporar”. 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 și Anton Zeilinger. „Mergând dincolo de teorema lui Bell”. În Menas Kafatos, editor, Teorema lui Bell, Teoria cuantică și Concepțiile Universului. Paginile 69–72. Dordrecht (1989). Springer Olanda.
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 și Clément Javerzac-Galy. „Algoritmi cuantici eficienți pentru statele GHZ și W și implementare pe computerul cuantic IBM”. Advanced Quantum Technologies 2, 1900015 (2019).
https: / / doi.org/ 10.1002 / qute.201900015

[53] RF Werner și MM Wolf. „Inegalități de corelație clopot multipartite pentru două observabile dihotomice per site”. Fiz. Rev. A 64, 032112 (2001).
https: / / doi.org/ 10.1103 / PhysRevA.64.032112

[54] Ryan O'Donnell. „Analiza funcțiilor booleene”. 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 și Vladimir V. Podolskii. „Complexitatea arborelui decizional de paritate este mai mare decât granularitatea” (2018). arXiv:1810.08668.
arXiv: 1810.08668

[56] A Canteaut și M Videau. „Funcții booleene simetrice”. IEEE Transactions on Information Theory 51, 2791–2811 (2005).
https: / / doi.org/ 10.1109 / TIT.2005.851743

[57] Larry J Stockmeyer. „Despre complexitatea combinațională a anumitor funcții booleene simetrice”. Teoria sistemelor matematice 10, 323–336 (1976).
https: / / doi.org/ 10.1007 / BF01683282

[58] RF Arnold și MA Harrison. „Proprietăți algebrice ale funcțiilor booleene simetrice și parțial simetrice”. IEEE Transactions on Electronic Computers EC-12, 244–251 (1963).
https://​/​doi.org/​10.1109/​PGEC.1963.263535

[59] An Braeken și Bart Preneel. „Despre imunitatea algebrică a funcțiilor booleene simetrice”. În Subhamoy Maitra, CE Veni Madhavan și Ramarathnam Venkatesan, editori, Progress in Cryptology – INDOCRYPT 2005. Volumul 3797 din Lecture Notes in Computer Science, paginile 35–48. Berlin, Heidelberg (2005). Springer Berlin Heidelberg.
https: / / doi.org/ 10.1007 / 11596219_4

[60] Harry Buhrman și Ronald de Wolf. „Măsuri de complexitate și complexitatea arborelui de decizie: un sondaj”. Teoretică Informatică 288, 21–43 (2002).
https:/​/​doi.org/​10.1016/​S0304-3975(01)00144-X

[61] Matthew Amy, Dmitri Maslov, Michele Mosca și Martin Roetteler. „Un algoritm de întâlnire la mijloc pentru sinteza rapidă a circuitelor cuantice optime de adâncime”. 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 și IL Markov. „Sinteza circuitelor logice cuantice”. 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 și Martti M Salomaa. „Descompunerea eficientă a porților cuantice”. Fiz. Rev. Lett. 92, 177902 (2004).
https: / / doi.org/ 10.1103 / PhysRevLett.92.177902

[64] Bei Zeng, Xie Chen și Isaac L Chuang. „Operațiuni semi-Clifford, structura ierarhiei $mathcal{C}_{k}$ și complexitatea porții pentru calculul cuantic tolerant la erori”. Fiz. Rev. A 77, 042313 (2008).
https: / / doi.org/ 10.1103 / PhysRevA.77.042313

[65] Gary J Mooney, Charles D Hill și Lloyd CL Hollenberg. „Sinteza porții cu un singur qubit optimă în funcție de cost în ierarhia Clifford”. Quantum 5, 396 (2021).
https:/​/​doi.org/​10.22331/​q-2021-02-15-396

[66] Nadish de Silva. „Teleportare eficientă pe poartă cuantică în dimensiuni superioare”. Proceedings of the Royal Society A 477, 20200865 (2021).
https: / / doi.org/ 10.1098 / rspa.2020.0865

[67] Daniel Gottesman și Isaac L Chuang. „Demonstrarea viabilității calculului cuantic universal folosind operații de teleportare și un singur qubit”. Nature 402, 390–393 (1999).
https: / / doi.org/ 10.1038 / 46503

[68] Daniel Gottesman. „Reprezentarea Heisenberg a calculatoarelor cuantice” (1998). arXiv:quant-ph/​9807006.
arXiv: Quant-ph / 9807006

[69] Vadym Kliuchnikov, Dmitri Maslov și Michele Mosca. „Sinteza exactă rapidă și eficientă a unităților cu un singur qubit generate de porțile Clifford și t”. Informații cuantice. Calculator. 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 și Tamás Vértesi. „Testarea structurii încrucișării multipartite cu inegalități clopot”. Fiz. Rev. Lett. 108, 110501 (2012).
https: / / doi.org/ 10.1103 / PhysRevLett.108.110501

[71] Julia Kempe, Hirotada Kobayashi, Keiji Matsumoto, Ben Toner și Thomas Vidick. „Jocurile încurcate sunt greu de aproximat”. SIAM Journal on Computing 40, 848–877 (2011).
https: / / doi.org/ 10.1137 / 090751293

[72] Yihui Quek, Eneet Kaur și Mark M. Wilde. „Estimarea urmelor multivariate în adâncime cuantică constantă”. Quantum 8, 1220 (2024).
https:/​/​doi.org/​10.22331/​q-2024-01-10-1220

[73] Peter Selinger. „Aproximarea eficientă Clifford+T a operatorilor cu un singur qubit”. Informații cuantice. Calculator. 15, 159–180 (2015).

[74] Vadym Kliuchnikov, Dmitri Maslov și Michele Mosca. „Aproximarea practică a unitarelor cu un singur qubit prin circuitele Clifford și T cuantice cu un singur qubit”. IEEE Transactions on Computers 65, 161–172 (2016).
https: / / doi.org/ 10.1109 / TC.2015.2409842

[75] Neil J Ross. „Aproximația optimă CLIFFORD+V fără ancillare a rotațiilor Z”. Informații cuantice. Calculator. 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 și Umesh Vazirani. „Teoria complexității cuantice”. În Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing. Paginile 11–20. STOC '93New York, NY, SUA (1993). Asociația pentru Mașini de Calcul.
https: / / doi.org/ 10.1145 / 167088.167097

[77] Alex Bocharov, Martin Roetteler și Krysta M Svore. „Sinteza eficientă a circuitelor cuantice probabilistice cu fallback”. Fiz. Rev. A 91, 052317 (2015).
https: / / doi.org/ 10.1103 / PhysRevA.91.052317

[78] Alex Bocharov, Martin Roetteler și Krysta M Svore. „Sinteza eficientă a circuitelor cuantice universale cu repetare până la succes”. Fiz. Rev. Lett. 114, 080502 (2015).
https: / / doi.org/ 10.1103 / PhysRevLett.114.080502

[79] Ingo Wegener. „Complexitatea funcțiilor booleene”. John Wiley $&$ Sons, Inc. SUA (1987).

[80] Heribert Vollmer. „Introducere în complexitatea circuitelor: o abordare uniformă”. Springer Publishing Company, Incorporated. (2010). editia 1. 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. „Metode algebrice în teoria limitelor inferioare pentru complexitatea circuitului boolean”. În lucrările celui de-al XIX-lea simpozion anual ACM privind teoria calculului. Paginile 77–82. STOC '87New York, NY, SUA (1987). Asociația pentru Mașini de Calcul.
https: / / doi.org/ 10.1145 / 28395.28404

[82] Jaikumar Radhakrishnan. „Limite mai bune pentru formulele de prag”. În [1991] Proceedings 32th Annual Symposium of Foundations of Computer Science. Paginile 314–323. IEEE Computer Society (1991).
https: / / doi.org/ 10.1109 / SFCS.1991.185384

[83] Michael J Fischer, Albert R Meyer și Michael S Paterson. „$Omega(Nlog n)$ Limite inferioare ale lungimii formulelor booleene”. SIAM J. Comput. 11, 416–427 (1982).
https: / / doi.org/ 10.1137 / 0211033

[84] Sanjeev Arora și Boaz Barak. „Complexitatea computațională: o abordare modernă”. Cambridge University Press. SUA (2009). editia I. url: https://​/​dl.acm.org/​doi/​abs/​1/​10.5555.
https: / / dl.acm.org/ doi / ABS / 10.5555 / 1540612

[85] Scott Aaronson. „De câtă structură este necesară pentru accelerarea cuantică uriașă?” (2022). arXiv:2209.06930.
arXiv: 2209.06930

[86] David A Barrington. „Programele de ramificare cu lățime delimitată de dimensiune polinomială recunosc exact acele limbaje în NC1”. Journal of Computer and System Sciences 38, 150–164 (1989).
https:/​/​doi.org/​10.1016/​0022-0000(89)90037-8

[87] Scott Aaronson și Alex Arkhipov. „Complexitatea computațională a opticii liniare”. În lucrările celui de-al patruzeci și treilea simpozion anual ACM privind teoria calculului. Paginile 333–342. STOC '11New York, NY, SUA (2011). Asociația pentru Mașini de Calcul.
https: / / doi.org/ 10.1145 / 1993636.1993682

[88] Peter W Shor. „Algoritmi de timp polinomial pentru factorizarea primilor și logaritmi discreti pe un computer cuantic”. SIAM Review 41, 303–332 (1999).
https: / / doi.org/ 10.1137 / S0036144598347011

[89] Daniel R Simon. „Despre puterea calculului cuantic”. 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 și Unger Falk. „Limitarea nonlocalității în orice lume în care complexitatea comunicării nu este trivială”. Fiz. Rev. Lett. 96, 250401 (2006).
https: / / doi.org/ 10.1103 / PhysRevLett.96.250401

[91] Wim van Dam. „Consecințele neplauzibile ale nonlocalității superputernice”. Natural Computing 12, 9–12 (2013).
https:/​/​doi.org/​10.1007/​s11047-012-9353-6

[92] Matthew Amy și Michele Mosca. „Optimizare T-Count și coduri Reed-Muller”. IEEE Transactions on Information Theory 65, 4771–4784 (2019).
https: / / doi.org/ 10.1109 / TIT.2019.2906374

[93] Peter Bürgisser, Michael Clausen și Mohammad A Shokrollahi. „Teoria complexității algebrice”. Volumul 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 și Isaac L. Chuang. „Simulare hamiltoniană optimă prin procesarea semnalului cuantic”. Fiz. Rev. Lett. 118, 010501 (2017).
https: / / doi.org/ 10.1103 / PhysRevLett.118.010501

[95] Jeongwan Haah. „Descompunerea produsului a funcțiilor periodice în procesarea semnalului cuantic”. Quantum 3, 190 (2019).
https:/​/​doi.org/​10.22331/​q-2019-10-07-190

[96] Scott Aaronson, Shalev Ben-David, Robin Kothari, Shravas Rao și Avishay Tal. „Grad versus gradul aproximativ și implicațiile cuantice ale teoremei de sensibilitate a lui Huang”. În Proceedings of the 53th Annual ACM SIGACT Symposium on Theory of Computing. Paginile 1330–1342. STOC 2021New York, NY, SUA (2021). Asociația pentru Mașini de Calcul.
https: / / doi.org/ 10.1145 / 3406325.3451047

[97] Hao Huang. „Subgrafe induse ale hipercuburilor și o dovadă a Conjecturii de Sensibilitate”. Analele matematicii 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 și Juris Smotrovs. „Separații în complexitatea interogărilor pe baza funcțiilor pointerului”. J. ACM 64 (2017).
https: / / doi.org/ 10.1145 / 3106234

[99] Peter Høyer și Robert Špalek. „Circuite cuantice cu fan-out nelimitat”. În Helmut Alt și Michel Habib, editori, STACS 2003. Paginile 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 și Akimasa Miyake. „Avantaj computațional cuantic atestat de jocurile nelocale cu starea clusterului ciclic”. Fiz. Rev. Research 4, 033068 (2022).
https: / / doi.org/ 10.1103 / PhysRevResearch.4.033068

[101] Paul Herringer și Robert Raussendorf. „Clasificarea firului cuantic bazat pe măsurare în stabilizatorul PEPS”. Quantum 7, 1041 (2023).
https:/​/​doi.org/​10.22331/​q-2023-06-12-1041

[102] Abhishek Anand. „Despre puterea circuitelor clasice și cuantice de mică adâncime întrețesate”. Teza de masterat. Universitatea din Waterloo. (2022). url: https://​/​uwspace.uwaterloo.ca/​handle/​10012/​18805.
https://​/​uwspace.uwaterloo.ca/​handle/​10012/​18805

[103] John Preskill. „Calcul cuantic în era NISQ și nu numai”. Quantum 2, 79 (2018).
https:/​/​doi.org/​10.22331/​q-2018-08-06-79

[104] Bülent Demirel, Weikai Weng, Christopher Thalacker, Matty Hoban și Stefanie Barz. „Corelații pentru calcul și calcul pentru corelații”. npj Quantum Information 7, 1–8 (2021).
https:/​/​doi.org/​10.1038/​s41534-020-00354-2

[105] Manoranjan Swain, Amit Rai, Bikash K Behera și Prasanta K Panigrahi. „Demonstrarea experimentală a încălcărilor inegalităților lui Mermin și Svetlichny pentru statele W și GHZ”. Procesarea informațiilor cuantice 18, 218 (2019).
https:/​/​doi.org/​10.1007/​s11128-019-2331-5

[106] Bo Yang, Rudy Raymond, Hiroshi Imai, Hyungseok Chang și Hidefumi Hiraishi. „Testarea inegalităților scalabile de tip clopot pentru stările grafice cuantice pe dispozitivele cuantice ibm”. 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 și A. Acín. „Inegalități scalabile pentru stările graficului qubit și autotestare robustă”. Fiz. 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 și Sarah Sheldon. „Verificarea stărilor Greenberger-Horne-Zeilinger încurcate multipartite prin mai multe coerențe cuantice”. Fiz. 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 și Ching-Ray Chang. „Inegalitățile lui Mermin ale mai multor qubiți cu măsurători ortogonale pe sistemul IBM Q 53-qubit”. Quantum Engineering 2, e45 (2020).
https://​/​doi.org/​10.1002/​que2.45

[110] Meron Sheffer, Daniel Azses și Emanuele G Dalla Torre. „Jucați jocuri cuantice nonlocale cu șase qubiți zgomotoși pe cloud”. Advanced Quantum Technologies 5, 2100081 (2022).
https: / / doi.org/ 10.1002 / qute.202100081

[111] Vedran Dunjko, Theodoros Kapourniotis și Elham Kashefi. „Calcul clasic cuantic securizat și delegat”. Informații cuantice. Calculator. 16, 61–86 (2016).

[112] Stefanie Barz, Vedran Dunjko, Florian Schlederer, Merritt Moore, Elham Kashefi și Ian A. Walmsley. „Calcul delegat îmbunătățit folosind coerență”. Fiz. 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 și Stefanie Barz. „Calcul multipartit clasic folosind resurse cuantice”. Physical Review A 96, 062317 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.96.062317

[114] Nasir Ahmed și Kamisetty Ramamohan Rao. „Transformarea Walsh-Hadamard”. În transformări ortogonale pentru procesarea semnalului digital. Paginile 99–152. Springer (1975).

[115] Michael A Nielsen și Isaac L Chuang. „Calcul cuantic și informații cuantice: ediția a 10-a aniversare”. Cambridge University Press. (2010).
https: / / doi.org/ 10.1017 / CBO9780511976667

[116] Philip Feinsilver și Jerzy Kocik. „Polonoame Krawtchouk și matrice Krawtchouk”. Paginile 115–141. Progrese recente în probabilitatea aplicată. Springer SUA. Boston, MA (2005).
https:/​/​doi.org/​10.1007/​0-387-23394-6_5

[117] Philip Feinsilver și Rene Schott. „Krawtchouk se transformă și convoluționează”. Buletin de Științe MatematicePagini 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 și IA Walmsley. „Interferența cuantică permite procesarea informațiilor cuantice în timp constant”. Science Advances 5, eaau9674 (2019).
https://​/​doi.org/​10.1126/​sciadv.aau9674

[119] Ravindran Kannan și Achim Bachem. „Algoritmi polinomii pentru calcularea formelor normale Smith și Hermite ale unei matrice întregi”. SIAM Journal on Computing 8, 499–507 (1979).
https: / / doi.org/ 10.1137 / 0208040

[120] Josh Alman și Virginia Vassilevska Williams. „O metodă laser rafinată și o multiplicare mai rapidă a matricei”. În Proceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms. Pagina 522–539. SODA '21USA (2021). Societatea de Matematică Industrială și Aplicată.
https: / / doi.org/ 10.1137 / 1.9781611976465.32

Citat de

Acest Lucru este publicat în Quantum sub Creative Commons Atribuire 4.0 internațională (CC BY 4.0) licență. Drepturile de autor rămân la deținătorii de drepturi de autor originale, precum autorii sau instituțiile lor.

Timestamp-ul:

Mai mult de la Jurnalul cuantic