Vantaggio quantistico nel calcolo quantistico basato su misurazioni temporalmente piatte

Ripubblicato da Platone

Seguaci: 0

Michele de Oliveira^1,2,3, Luis S. Barbosa^1,2,3ed Ernesto F. Galvão^3,4

¹Università del Minho, Dipartimento di Informatica, Braga, Portogallo
²INESC TEC, Braga, Portogallo
³Laboratorio Internazionale di Nanotecnologia Iberica (INL) Av. Mestre Jose Veiga, 4715-330, Braga, Portogallo
⁴Istituto di fisica, Universidade Federal Fluminense Av. Gal. Milton Tavares de Souza s/n, Niterói, RJ, 24210-340, Brasile

Trovi questo documento interessante o vuoi discuterne? Scrivi o lascia un commento su SciRate.

Astratto

È stato dimostrato che diverse classi di circuiti quantistici forniscono un vantaggio computazionale quantistico sotto determinati presupposti. Lo studio di classi sempre più ristrette di circuiti quantistici capaci di vantaggio quantistico è motivato da possibili semplificazioni nelle dimostrazioni sperimentali. In questo articolo studiamo l'efficienza del calcolo quantistico basato su misurazioni con un ordinamento temporale delle misurazioni completamente piatto. Proponiamo nuove costruzioni per il calcolo deterministico di funzioni booleane arbitrarie, attingendo alle correlazioni presenti negli stati multi-qubit Greenberger, Horne e Zeilinger (GHZ). Caratterizziamo la complessità della misurazione necessaria utilizzando la gerarchia di Clifford e generalmente riduciamo anche il numero di qubit necessari rispetto alle costruzioni precedenti. In particolare, identifichiamo una famiglia di funzioni booleane per le quali è possibile una valutazione deterministica utilizzando MBQC non adattivo, caratterizzate da un vantaggio quantistico in ampiezza e numero di porte rispetto ai circuiti classici.

Vantaggio quantistico nel calcolo quantistico basato su misurazioni temporalmente piatte PlatoBlockchain Data Intelligence. Ricerca verticale. Ai.

Immagine in primo piano: il modello MBQC non adattivo può essere descritto da un'architettura computazionale specifica divisa nel processo di preparazione dello stato quantistico, nella routine di misurazione e nell'elaborazione lineare pre e post-classica associata (in alto a sinistra). Questo modello facilita lo studio dei requisiti di risorse per valutare le funzioni booleane simmetriche in termini di numero asintotico di qubit e operazioni richieste (in alto a destra). Questi elementi rivelano i nostri risultati principali [in basso], che sono articolati per insiemi di porte classiche e quantistiche standard e descrizioni di circuiti [in basso a sinistra], che caratterizzano l'insieme di funzioni booleane che dimostrano un vantaggio quantistico rispetto al numero di porte e alla larghezza delle circuiti (in basso a destra).

[Contenuto incorporato]

Riepilogo popolare

L’informatica quantistica promette di offrire vantaggi computazionali rispetto ai migliori algoritmi classici per molti compiti. Risultati rigorosi che quantificano questo vantaggio sono rari e aiutano a concentrare la ricerca sulle risorse quantistiche cruciali che offrono prestazioni migliori di quelle classiche. Questo vantaggio quantistico può verificarsi rispetto a diverse risorse: il numero totale di porte richieste, la profondità dei circuiti risultanti o la dimensione della memoria utilizzata (nota come larghezza del circuito).

In questo lavoro analizziamo la valutazione delle funzioni booleane, qualcosa che i computer quantistici possono fare utilizzando i risultati correlati delle misurazioni sugli stati Greenberger-Horne-Zeilinger (GHZ) entangled di molti qubit. Questa variante del calcolo quantistico basato sulla misurazione non richiede adattività, quindi tutti i qubit possono essere misurati simultaneamente. Questa struttura temporale piatta del processo computazionale si traduce, in alcuni casi, in circuiti quantistici molto economici. Identifichiamo le caratteristiche di una funzione booleana che determinano quanti qubit sono necessari e la precisione di misurazione richiesta. Per una particolare famiglia di funzioni booleane mostriamo che esiste un rigoroso vantaggio in larghezza e numero di porte rispetto alla corrispondente famiglia di circuiti classici. In futuro, le nostre tecniche potrebbero aiutare a ideare modi migliori di utilizzo delle risorse quantistiche anche per circuiti adattivi che mostrano maggiore espressività computazionale.

► dati BibTeX

@articolo{Oliveira2024quantumadvantagein, doi = {10.22331/q-2024-04-09-1312}, URL = {https://doi.org/10.22331/q-2024-04-09-1312}, titolo = {Vantaggio quantistico nel calcolo quantistico basato su misurazioni temporalmente piatte}, autore = {Oliveira, Michael de e Barbosa, Lu{'{i}}s S. e Galv{~{a}}o, Ernesto F.}, diario = {{Quantum}}, issn = {2521-327X}, editore = {{Verein zur F{“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {8}, pagine = {1312}, mese = aprile, anno = {2024} }

► Riferimenti

, Scott Aaronson, DeVon Ingram e William Kretschmer. “Le acrobazie del BQP”. In Shachar Lovett, redattore, 37a conferenza sulla complessità computazionale (CCC 2022). Volume 234 di Leibniz International Proceedings in Informatics (LIPIcs), pagine 20: 1–20: 17. Dagstuhl, Germania (2022). Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
https: / / doi.org/ 10.4230 / LIPIcs.CCC.2022.20

, Richard Jozsa e Noah Linden. "Sul ruolo dell'entanglement nell'accelerazione quantistica-computazionale". Atti della Royal Society di Londra. Serie A: Scienze matematiche, fisiche e ingegneristiche 459, 2011–2032 (2003).
https: / / doi.org/ 10.1098 / rspa.2002.1097

, Mark Howard, Joel Wallman, Victor Veitch e Joseph Emerson. “La contestualità fornisce la 'magia' per il calcolo quantistico”. Natura 510, 351–355 (2014).
https: / / doi.org/ 10.1038 / nature13460

, Juan Bermejo-Vega, Nicolas Delfosse, Dan E. Browne, Cihan Okay e Robert Raussendorf. “La contestualità come risorsa per modelli di calcolo quantistico con qubit”. Fis. Rev. Lett. 119, 120505 (2017).
https: / / doi.org/ 10.1103 / PhysRevLett.119.120505

, Ernesto F. Galvão. "Funzioni Wigner discrete e accelerazione computazionale quantistica". Fis. Rev. A 71, 042302 (2005).
https: / / doi.org/ 10.1103 / PhysRevA.71.042302

, A. Mari e J. Eisert. "Le funzioni di Wigner positive rendono efficiente la simulazione classica del calcolo quantistico". Fis. Rev. Lett. 109, 230503 (2012).
https: / / doi.org/ 10.1103 / PhysRevLett.109.230503

, Lov K. Grover. “I vantaggi della sovrapposizione”. Scienza 280, 228–228 (1998).
https: / / doi.org/ 10.1126 / science.280.5361.228

, Robert Raussendorf e Hans J. Briegel. "Un computer quantistico unidirezionale". Fis. Rev. Lett. 86, 5188–5191 (2001).
https: / / doi.org/ 10.1103 / PhysRevLett.86.5188

, Maarten Van den Nest, Akimasa Miyake, Wolfgang Dür e Hans J. Briegel. “Risorse universali per il calcolo quantistico basato su misurazioni”. Fis. Rev. Lett. 97, 150504 (2006).
https: / / doi.org/ 10.1103 / PhysRevLett.97.150504

, Janet Anders e Dan E. Browne. “Potere computazionale delle correlazioni”. Fis. Rev. Lett. 102, 050502 (2009).
https: / / doi.org/ 10.1103 / PhysRevLett.102.050502

, Vincent Danos e Elham Kashefi. “Il determinismo nel modello unidirezionale”. Fis. Rev.A74, 052310 (2006).
https: / / doi.org/ 10.1103 / PhysRevA.74.052310

, Daniel E Browne, Elham Kashefi, Mehdi Mhalla e Simon Perdrix. "Flusso generalizzato e determinismo nel calcolo quantistico basato su misurazioni". Nuovo giornale di fisica 9, 250 (2007).
https://doi.org/10.1088/1367-2630/9/8/250

, Michael J Bremner, Ashley Montanaro e Dan J Shepherd. "Complessità del caso medio rispetto alla simulazione approssimativa dei calcoli quantistici pendolari". Fis. Rev. Lett. 117, 080501 (2016).
https: / / doi.org/ 10.1103 / PhysRevLett.117.080501

, Matty J. Hoban, Joel J. Wallman, Hussain Anwar, Naïri Usher, Robert Raussendorf e Dan E. Browne. “Calcolo classico basato sulla misurazione”. Fis. Rev. Lett. 112, 140505 (2014).
https: / / doi.org/ 10.1103 / PhysRevLett.112.140505

, Michael J. Bremner, Ashley Montanaro e Dan J. Shepherd. "Raggiungere la supremazia quantistica con calcoli quantistici pendolari sparsi e rumorosi". Quantistici 1, 8 (2017).
https://doi.org/10.22331/q-2017-04-25-8

, Leonardo Novo, Juani Bermejo-Vega e Raúl García-Patrón. "Vantaggio quantistico dalle misurazioni energetiche di sistemi quantistici a molti corpi". Quantico 5, 465 (2021).
https://doi.org/10.22331/q-2021-06-02-465

, Masahito Hayashi e Yuki Takeuchi. "Verifica dei calcoli quantistici di pendolarismo tramite stima fedele degli stati dei grafici ponderati". Nuovo giornale di fisica 21, 93060 (2019).
https://doi.org/10.1088/1367-2630/ab3d88

, Juan Bermejo-Vega, Dominik Hangleiter, Martin Schwarz, Robert Raussendorf e Jens Eisert. "Architetture per la simulazione quantistica che mostrano un'accelerazione quantistica". Fis. Rev.X8, 021010 (2018).
https: / / doi.org/ 10.1103 / PhysRevX.8.021010

, Jacob Miller, Stephen Sanders e Akimasa Miyake. "Supremazia quantistica nel calcolo basato su misurazioni in tempo costante: un'architettura unificata per campionamento e verifica". Fis. Rev. A 96, 062320 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.96.062320

, Matty J Hoban, Earl T Campbell, Klearchos Loukopoulos e Dan E Browne. "Calcolo quantistico basato su misurazioni non adattative e disuguaglianze di Bell multipartitiche". Nuovo giornale di fisica 13, 23014 (2011).
https://doi.org/10.1088/1367-2630/13/2/023014

, Ryuhei Mori. “Rappresentazione periodica di Fourier delle funzioni booleane”. Informazioni quantistiche. Calcola. 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 mila

, Markus Frembs, Sam Roberts, Earl T Campbell e Stephen D Bartlett. "Gerarchie di risorse per il calcolo quantistico basato su misurazioni". Nuovo giornale di fisica 25, 013002 (2023).
https:///doi.org/10.1088/1367-2630/acaee2

, Jelena Mackeprang, Daniel Bhatti, Matty J Hoban e Stefanie Barz. "Il potere dei qutrits per il calcolo quantistico basato su misurazioni non adattative". Nuovo giornale di fisica 25, 073007 (2023).
https:///doi.org/10.1088/1367-2630/acdf77

, Daniel Collins, Nicolas Gisin, Sandu Popescu, David Roberts e Valerio Scarani. "Disuguaglianza di tipo campana per rilevare la vera non separabilità di $mathit{n}$-Body". Fis. Rev. Lett. 88, 170405 (2002).
https: / / doi.org/ 10.1103 / PhysRevLett.88.170405

, Nicolas Brunner, Daniel Cavalcanti, Stefano Pironio, Valerio Scarani, and Stephanie Wehner. “Bell nonlocalità”. Rev.mod. Fis. 86, 419–478 (2014).
https: / / doi.org/ 10.1103 / RevModPhys.86.419

, Dmitrijs Kravčenko. "Giochi quantistici, stati quantistici, loro proprietà e applicazioni". Tesi di dottorato. Latvijas Universitate. (2013).

, William Slofstra. "Limiti inferiori dell'entanglement necessari per giocare a giochi XOR non locali". Giornale di fisica matematica 52, 102202 (2011).
https: / / doi.org/ 10.1063 / 1.3652924 mila

, Andris Ambainis, Jānis Iraids, Dmitry Kravchenko e Madars Virza. "Vantaggio delle strategie quantistiche nei giochi xor simmetrici casuali". In Antonín Kučera, Thomas A. Henzinger, Jaroslav Nešetřil, Tomáš Vojnar e David Antoš, editori, Mathematical and Engineering Methods in Computer Science. Pagine 57–68. Berlino, Heidelberg (2013). Springer Berlino Heidelberg.
https://doi.org/10.1007/978-3-642-36046-6_7

, Andris Ambainis e Janis Iraids. "Vantaggio dimostrabile per le strategie quantistiche nei giochi XOR simmetrici casuali". In Simone Severini e Fernando Brandao, curatori, 8a Conferenza sulla Teoria del Calcolo Quantistico, della Comunicazione e della Crittografia (TQC 2013). Volume 22 di Leibniz International Proceedings in Informatics (LIPIcs), pagine 146–156. Dagstuhl, Germania (2013). Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
https: / / doi.org/ 10.4230 / LIPIcs.TQC.2013.146

, Samuel Marcovitch e Benni Reznik. “Implicazioni della complessità della comunicazione nei sistemi multipartiti”. Fis. Rev.A77, 032120 (2008).
https: / / doi.org/ 10.1103 / PhysRevA.77.032120

, Marcin Pawłowski, Tomasz Paterek, Dagomir Kaszlikowski, Valerio Scarani, Andreas Winter e Marek Żukowski. “La causalità dell’informazione come principio fisico”. Natura 461, 1101–1104 (2009).
https: / / doi.org/ 10.1038 / nature08400

, Sandu Popescu e Daniel Rohrlich. "La non località quantistica come assioma". Fondamenti di fisica 24, 379–385 (1994).
https: / / doi.org/ 10.1007 / BF02058098

, Jonathan Barrett, Noah Linden, Serge Massar, Stefano Pironio, Sandu Popescu e David Roberts. "Le correlazioni non locali come risorsa teorica dell'informazione". Fis. Rev. A 71, 022101 (2005).
https: / / doi.org/ 10.1103 / PhysRevA.71.022101

, AA Razborov. “Complessità della comunicazione quantistica di predicati simmetrici”. Izvestiya: Matematica 67, 145 (2003).
https://doi.org/10.1070/IM2003v067n01ABEH000422

, Zhiqiang Zhang e Yaoyun Shi. "Complessità di comunicazione delle funzioni XOR simmetriche". Informazioni quantistiche e calcolo 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 mila

, Pierre Botterón. "Scatole non locali e complessità della comunicazione". Tesi di master. Università Paul Sabatier Tolosa 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

, Kwangil Bae e Wonmin Son. "Criteri di nonlocalità generalizzati sotto la simmetria di correlazione". Fis. Rev. A 98, 022116 (2018).
https: / / doi.org/ 10.1103 / PhysRevA.98.022116

, Markus Frembs, Sam Roberts e Stephen D. Bartlett. "La contestualità come risorsa per il calcolo quantistico basato sulla misurazione oltre i qubit". Nuovo giornale di fisica 20, 103011 (2018).
https: / / doi.org/ 10.1088 / 1367-2630 / aae3ad

, Sergey Bravyi, David Gosset e Robert König. "Vantaggio quantistico con circuiti superficiali". Scienza 362, 308–311 (2018).
https: / / doi.org/ 10.1126 / science.aar3106

, Daniel Grier e Luke Schaeffer. "Circuiti interattivi poco profondi di Clifford: vantaggio quantistico contro NC¹ e oltre". Negli atti del 52esimo simposio annuale ACM SIGACT sulla teoria dell'informatica. Pagine 875–888. STOC 2020New York, NY, Stati Uniti (2020). Associazione per le macchine informatiche.
https: / / doi.org/ 10.1145 / 3357713.3384332 mila

, Libor Caha, Xavier Coiteux-Roy, and Robert Koenig. "Il teletrasporto a porta singola qubit offre un vantaggio quantistico" (2022). arXiv:2209.14158.
arXiv: 2209.14158

, François Le Gall. "Vantaggio quantistico nel caso medio con circuiti poco profondi". In Amir Shpilka, redattore, 34a conferenza sulla complessità computazionale (CCC 2019). Volume 137 di Leibniz International Proceedings in Informatics (LIPIcs), pagine 21:1—21:20. Dagstuhl, Germania (2019). Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
https: / / doi.org/ 10.4230 / LIPIcs.CCC.2019.21

, Matthew Coudron, Jalex Stark e Thomas Vidick. “Scambiare località per tempo: casualità certificabile da circuiti a bassa profondità”. Comunicazioni in fisica matematica 382, 49–86 (2021).
https: / / doi.org/ 10.1007 / s00220-021-03963-w

, Sergey Bravyi, David Gosset, Robert König e Marco Tomamichel. "Vantaggio quantistico con circuiti poco profondi e rumorosi". Fisica della natura 16, 1040–1045 (2020).
https: / / doi.org/ 10.1038 / s41567-020-0948-z

, Atsuya Hasegawa e François Le Gall. "Vantaggio quantistico con circuiti poco profondi sotto corruzione arbitraria". In Hee-Kap Ahn e Kunihiko Sadakane, editori, 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Volume 212 di Leibniz International Proceedings in Informatics (LIPIcs), pagine 74: 1–74: 16. Dagstuhl, Germania (2021). Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPICs.ISAAC.2021.74

, Adam Bene Watts, Robin Kothari, Luke Schaeffer e Avishay Tal. "Separazione esponenziale tra circuiti quantistici superficiali e circuiti classici superficiali illimitati a ventaglio". Negli atti del 51° simposio annuale ACM SIGACT sulla teoria dell'informatica. Pagine 515–526. STOC 2019New York, NY, Stati Uniti (2019). Associazione per le macchine informatiche.
https: / / doi.org/ 10.1145 / 3313276.3316404 mila

, Natalie Parham. "Sulla potenza e sui limiti dei circuiti quantistici superficiali". Tesi di master. Università di Waterloo. (2022). URL: https:///uwspace.uwaterloo.ca/handle/10012/18702.
https:///uwspace.uwaterloo.ca/handle/10012/18702

, Dmitri Maslov, Jin-Sung Kim, Sergey Bravyi, Theodore J Yoder e Sarah Sheldon. “Vantaggio quantistico per calcoli con spazio limitato”. Fisica della natura 17, 894–897 (2021).
https://doi.org/10.1038/s41567-021-01271-7

, Farid Ablayev, Aida Gainutdinova, Marek Karpinski, Cristopher Moore e Christopher Pollett. "Sulla potenza computazionale del programma probabilistico e di ramificazione quantistica". Informazioni e calcolo 203, 145–162 (2005).
https: / / doi.org/ 10.1016 / j.ic.2005.04.003

, D Shepherd e MJ Bremner. “Calcolo quantistico temporalmente non strutturato”. Atti della Royal Society of London Serie A 465, 1413–1439 (2009).
https: / / doi.org/ 10.1098 / rspa.2008.0443

, Daniel M Greenberger, Michael A Horne e Anton Zeilinger. “Andare oltre il teorema di Bell”. In Menas Kafatos, editore, Teorema di Bell, teoria quantistica e concezioni dell'universo. Pagine 69–72. Dordrecht (1989). Springer Paesi Bassi.
https://doi.org/10.1007/978-94-017-0849-4_10

, Diogo Cruz, Romain Fournier, Fabien Gremion, Alix Jeannerot, Kenichi Komagata, Tara Tosic, Jarla Thiesbrummel, Chun Lam Chan, Nicolas Macris, Marc-André Dupertuis e Clément Javerzac-Galy. "Algoritmi quantistici efficienti per stati GHZ e W e implementazione sul computer quantistico IBM". Tecnologie quantistiche avanzate 2, 1900015 (2019).
https: / / doi.org/ 10.1002 / qute.201900015

, RF Werner e MM Lupo. "Disuguaglianze di correlazione a campana multipartite per due osservabili dicotomici per sito". Fis. Rev. A 64, 032112 (2001).
https: / / doi.org/ 10.1103 / PhysRevA.64.032112

, Ryan O'Donnell. “Analisi delle funzioni booleane”. Stampa dell'Università di Cambridge. (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

, Anastasiya Chistopolskaya e Vladimir V. Podolskii. “La complessità dell’albero decisionale della parità è maggiore della granularità” (2018). arXiv:1810.08668.
arXiv: 1810.08668

, A Canteaut e M Videau. “Funzioni booleane simmetriche”. Transazioni IEEE sulla teoria dell'informazione 51, 2791–2811 (2005).
https: / / doi.org/ 10.1109 / TIT.2005.851743

, Larry J. Stockmeyer. "Sulla complessità combinatoria di alcune funzioni booleane simmetriche". Teoria dei sistemi matematici 10, 323–336 (1976).
https: / / doi.org/ 10.1007 / BF01683282

, RF Arnold e MA Harrison. "Proprietà algebriche delle funzioni booleane simmetriche e parzialmente simmetriche". Transazioni IEEE sui computer elettronici EC-12, 244–251 (1963).
https:///doi.org/10.1109/PGEC.1963.263535

, Un Braeken e Bart Preneel. "Sull'immunità algebrica delle funzioni booleane simmetriche". In Subhamoy Maitra, CE Veni Madhavan e Ramarathnam Venkatesan, editori, Progress in Cryptology – INDOCRYPT 2005. Volume 3797 di Lecture Notes in Computer Science, pagine 35–48. Berlino, Heidelberg (2005). Springer Berlino Heidelberg.
https: / / doi.org/ 10.1007 / 11596219_4

, Harry Buhrman e Ronald de Wolf. “Misure di complessità e complessità dell’albero decisionale: un’indagine”. Informatica teorica 288, 21–43 (2002).
https://doi.org/10.1016/S0304-3975(01)00144-X

, Matthew Amy, Dmitri Maslov, Michele Mosca e Martin Roetteler. "Un algoritmo Meet-in-the-Middle per la sintesi rapida di circuiti quantistici con profondità ottimale". Transazioni IEEE sulla progettazione assistita da computer di circuiti e sistemi integrati 32, 818–830 (2013).
https: / / doi.org/ 10.1109 / TCAD.2013.2244643

, VV Shende, SS Bullock e IL Markov. “Sintesi di circuiti logici quantistici”. Transazioni IEEE sulla progettazione assistita da computer di circuiti e sistemi integrati 25, 1000–1010 (2006).
https: / / doi.org/ 10.1109 / TCAD.2005.855930

, Juha J Vartiainen, Mikko Möttönen e Martti M Salomaa. "Decomposizione efficiente delle porte quantistiche". Fis. Rev. Lett. 92, 177902 (2004).
https: / / doi.org/ 10.1103 / PhysRevLett.92.177902

, Bei Zeng, Xie Chen e Isaac L Chuang. "Operazioni di Semi-Clifford, struttura della gerarchia $mathcal{C}_{k}$ e complessità del gate per il calcolo quantistico tollerante agli errori". Fis. Rev.A77, 042313 (2008).
https: / / doi.org/ 10.1103 / PhysRevA.77.042313

, Gary J Mooney, Charles D Hill e Lloyd CL Hollenberg. "Sintesi di porte a qubit singolo economicamente ottimale nella gerarchia di Clifford". Quantico 5, 396 (2021).
https://doi.org/10.22331/q-2021-02-15-396

, Nadish de Silva. “Teletrasporto efficiente della porta quantistica nelle dimensioni superiori”. Atti della Royal Society A 477, 20200865 (2021).
https: / / doi.org/ 10.1098 / rspa.2020.0865

, Daniel Gottesman e Isaac L. Chuang. "Dimostrare la fattibilità del calcolo quantistico universale utilizzando il teletrasporto e le operazioni a singolo qubit". Natura 402, 390–393 (1999).
https: / / doi.org/ 10.1038 / 46503 mila

, Daniele Gottesmann. “La rappresentazione di Heisenberg dei computer quantistici” (1998). arXiv:quant-ph/9807006.
arXiv: Quant-ph / 9807006

, Vadym Kliuchnikov, Dmitri Maslov e Michele Mosca. "Sintesi esatta veloce ed efficiente di unitari a singolo qubit generati da clifford e t gate". Informazioni quantistiche. Calcola. 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 mila

, Nicolas Brunner, James Sharam e Tamás Vértesi. "Testare la struttura dell'entanglement multipartito con disuguaglianze di campana". Fis. Rev. Lett. 108, 110501 (2012).
https: / / doi.org/ 10.1103 / PhysRevLett.108.110501

, Julia Kempe, Hirotada Kobayashi, Keiji Matsumoto, Ben Toner e Thomas Vidick. "I giochi intrecciati sono difficili da approssimare". SIAM Journal on Computing 40, 848–877 (2011).
https: / / doi.org/ 10.1137 / 090751293 mila

, Yihui Quek, Eneet Kaur e Mark M. Wilde. “Stima multivariata di tracce a profondità quantistica costante”. Quantico 8, 1220 (2024).
https://doi.org/10.22331/q-2024-01-10-1220

, Pietro Selinger. "Efficiente approssimazione Clifford+T degli operatori a Qubit singolo". Informazioni quantistiche. Calcola. 15, 159–180 (2015).

, Vadym Kliuchnikov, Dmitri Maslov e Michele Mosca. "Approssimazione pratica degli unitari a Qubit singolo mediante Clifford quantistico a Qubit singolo e circuiti T". Transazioni IEEE sui computer 65, 161–172 (2016).
https: / / doi.org/ 10.1109 / TC.2015.2409842

, Neil J Ross. "Approssimazione ottimale CLIFFORD + V senza ancilla delle rotazioni Z". Informazioni quantistiche. Calcola. 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 mila

, Ethan Bernstein e Umesh Vazirani. “Teoria della complessità quantistica”. In Atti del venticinquesimo simposio annuale ACM sulla teoria dell'informatica. Pagine 11–20. STOC '93New York, NY, USA (1993). Associazione per le macchine informatiche.
https: / / doi.org/ 10.1145 / 167088.167097 mila

, Alex Bocharov, Martin Roetteler e Krysta M Svore. “Sintesi efficiente di circuiti quantistici probabilistici con fallback”. Fis. Rev. A 91, 052317 (2015).
https: / / doi.org/ 10.1103 / PhysRevA.91.052317

, Alex Bocharov, Martin Roetteler e Krysta M Svore. "Sintesi efficiente di circuiti quantistici universali che si ripetono fino al successo". Fis. Rev. Lett. 114, 080502 (2015).
https: / / doi.org/ 10.1103 / PhysRevLett.114.080502

, Ingo Wegener. "La complessità delle funzioni booleane". John Wiley $&$ Sons, Inc.Stati Uniti (1987).

, Heribert Vollmer. "Introduzione alla complessità dei circuiti: un approccio uniforme". Società editrice Springer, Incorporata. (2010). 1a edizione. 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

, R. Smolenskij. "Metodi algebrici nella teoria dei limiti inferiori per la complessità dei circuiti booleani". In Atti del diciannovesimo simposio annuale ACM sulla teoria dell'informatica. Pagine 77–82. STOC '87New York, NY, USA (1987). Associazione per le macchine informatiche.
https: / / doi.org/ 10.1145 / 28395.28404 mila

, Jaikumar Radhakrishnan. "Limiti migliori per le formule di soglia". In [1991] Atti del 32esimo Simposio annuale sui fondamenti dell'informatica. Pagine 314–323. Società informatica IEEE (1991).
https: / / doi.org/ 10.1109 / SFCS.1991.185384

, Michael J Fischer, Albert R Meyer e Michael S Paterson. "$Omega(Nlog n)$ Limiti inferiori sulla lunghezza delle formule booleane". SIAM J.Comput. 11, 416–427 (1982).
https: / / doi.org/ 10.1137 / 0211033 mila

, Sanjeev Arora e Boaz Barak. "Complessità computazionale: un approccio moderno". Stampa dell'Università di Cambridge. Stati Uniti (2009). 1a edizione. url: https:///dl.acm.org/doi/abs/10.5555/1540612.
https: / / dl.acm.org/ doi / abs / 10.5555 / 1540612 mila

, Scott Aaronson. “Quanta struttura è necessaria per enormi accelerazioni quantistiche?” (2022). arXiv:2209.06930.
arXiv: 2209.06930

, David A Barrington. "I programmi di branching di dimensioni polinomiali a larghezza limitata riconoscono esattamente quelle lingue in NC1". Journal of Computer and System Sciences 38, 150–164 (1989).
https://doi.org/10.1016/0022-0000(89)90037-8

, Scott Aaronson e Alex Arkhipov. "La complessità computazionale dell'ottica lineare". Negli Atti del quarantatreesimo simposio annuale ACM sulla teoria dell'informatica. Pagine 333–342. STOC '11New York, NY, Stati Uniti (2011). Associazione per le macchine informatiche.
https: / / doi.org/ 10.1145 / 1993636.1993682 mila

, Peter W. Shor. "Algoritmi polinomiali per la fattorizzazione prima e logaritmi discreti su un computer quantistico". Revisione SIAM 41, 303–332 (1999).
https: / / doi.org/ 10.1137 / S0036144598347011

, Daniele R Simon. "Sul potere del calcolo quantistico". SIAM Journal on Computing 26, 1474–1483 (1997).
https: / / doi.org/ 10.1137 / S0097539796298637

, Gilles Brassard, Harry Buhrman, Noah Linden, André Allan Méthot, Alain Tapp e Unger Falk. "Limite alla nonlocalità in qualsiasi mondo in cui la complessità della comunicazione non è banale". Fis. Rev. Lett. 96, 250401 (2006).
https: / / doi.org/ 10.1103 / PhysRevLett.96.250401

, Wim van Dam. “Conseguenze non plausibili della nonlocalità superforte”. Informatica naturale 12, 9–12 (2013).
https://doi.org/10.1007/s11047-012-9353-6

, Matthew Amy e Michele Mosca. "Ottimizzazione del conteggio T e codici Reed-Muller". Transazioni IEEE sulla teoria dell'informazione 65, 4771–4784 (2019).
https: / / doi.org/ 10.1109 / TIT.2019.2906374

, Peter Bürgisser, Michael Clausen e Mohammad A Shokrollahi. “Teoria algebrica della complessità”. Volume 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 mila

, Guang Hao Low e Isaac L. Chuang. "Simulazione hamiltoniana ottimale mediante elaborazione quantistica del segnale". Fis. Rev. Lett. 118, 010501 (2017).
https: / / doi.org/ 10.1103 / PhysRevLett.118.010501

, Jeongwan Haah. "Scomposizione del prodotto di funzioni periodiche nell'elaborazione dei segnali quantistici". Quantico 3, 190 (2019).
https://doi.org/10.22331/q-2019-10-07-190

, Scott Aaronson, Shalev Ben-David, Robin Kothari, Shravas Rao e Avishay Tal. "Grado vs. Grado approssimato e implicazioni quantistiche del teorema della sensibilità di Huang". Negli atti del 53° simposio annuale ACM SIGACT sulla teoria dell'informatica. Pagine 1330–1342. STOC 2021New York, NY, Stati Uniti (2021). Associazione per le macchine informatiche.
https: / / doi.org/ 10.1145 / 3406325.3451047 mila

, Hao Huang. "Sottografi indotti di ipercubi e dimostrazione della congettura di sensibilità". Annali di matematica 190, 949–955 (2019).
https: / / doi.org/ 10.4007 / annals.2019.190.3.6

, Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha e Juris Smotrovs. "Separazioni nella complessità delle query basate su funzioni puntatore". J. ACM 64 (2017).
https: / / doi.org/ 10.1145 / 3106234 mila

, Peter Høyer e Robert Špalek. “Circuiti quantistici con fan-out illimitato”. In Helmut Alt e Michel Habib, editori, STACS 2003. Pagine 234–246. Berlino, Heidelberg (2003). Springer Berlino Heidelberg.
https://doi.org/10.1007/3-540-36494-3_22

, Austin K Daniel, Yingyue Zhu, C Huerta Alderete, Vikas Buchemmavari, Alaina M Green, Nhung H Nguyen, Tyler G Thurtell, Andrew Zhao, Norbert M Linke e Akimasa Miyake. "Vantaggio computazionale quantistico attestato da giochi non locali con lo stato ciclico del cluster". Fis. Rev. Ricerca 4, 033068 (2022).
https: / / doi.org/ 10.1103 / PhysRevResearch.4.033068

, Paul Herringer e Robert Raussendorf. "Classificazione del filo quantistico basato sulla misurazione nello stabilizzatore PEPS". Quantico 7, 1041 (2023).
https://doi.org/10.22331/q-2023-06-12-1041

, Abhishek Anand. "Sulla potenza dei circuiti quantistici e classici interlacciati a bassa profondità". Tesi di master. Università di Waterloo. (2022). URL: https:///uwspace.uwaterloo.ca/handle/10012/18805.
https:///uwspace.uwaterloo.ca/handle/10012/18805

, Giovanni Preskill. "Quantum Computing nell'era NISQ e oltre". Quantum 2, 79 (2018).
https://doi.org/10.22331/q-2018-08-06-79

, Bülent Demirel, Weikai Weng, Christopher Thalacker, Matty Hoban e Stefanie Barz. “Correlazioni per il calcolo e calcolo per le correlazioni”. npj Informazioni quantistiche 7, 1–8 (2021).
https://doi.org/10.1038/s41534-020-00354-2

, Manoranjan Swain, Amit Rai, Bikash K Behera e Prasanta K Panigrahi. “Dimostrazione sperimentale delle violazioni delle disuguaglianze di Mermin e Svetlichny per gli stati W e GHZ”. Elaborazione delle informazioni quantistiche 18, 218 (2019).
https://doi.org/10.1007/s11128-019-2331-5

, Bo Yang, Rudy Raymond, Hiroshi Imai, Hyungseok Chang e Hidefumi Hiraishi. "Test di disuguaglianze di campana scalabili per stati di grafici quantistici su dispositivi quantistici IBM". IEEE Journal on Emerging and Selected Topics in Circuits and Systems 12, 638–647 (2022).
https:///doi.org/10.1109/JETCAS.2022.3201730

, F. Baccari, R. Augusiak, I. Šupić, J. Tura e A. Acín. "Disuguaglianze di campana scalabili per stati di grafici qubit e robusto autotest". Fis. Rev. Lett. 124, 020402 (2020).
https: / / doi.org/ 10.1103 / PhysRevLett.124.020402

, Ken X Wei, Isaac Lauer, Srikanth Srinivasan, Neereja Sundaresan, Douglas T McClure, David Toyli, David C McKay, Jay M Gambetta e Sarah Sheldon. "Verifica degli stati Greenberger-Horne-Zeilinger multipartiti entangled tramite molteplici coerenze quantistiche". Fis. Rev. A 101, 032343 (2020).
https: / / doi.org/ 10.1103 / PhysRevA.101.032343

, Wei-Jia Huang, Wei-Chen Chien, Chien-Hung Cho, Che-Chun Huang, Tsung-Wei Huang e Ching-Ray Chang. "Diseguaglianze di Mermin di più qubit con misurazioni ortogonali sul sistema IBM Q 53-qubit". Ingegneria Quantistica 2, e45 (2020).
https:///doi.org/10.1002/que2.45

, Meron Sheffer, Daniel Azses, and Emanuele G. Dalla Torre. "Giocare a giochi quantistici non locali con sei qubit rumorosi sul cloud". Tecnologie quantistiche avanzate 5, 2100081 (2022).
https: / / doi.org/ 10.1002 / qute.202100081

, Vedran Dunjko, Theodoros Kapourniotis e Elham Kashefi. "Calcolo classico delegato sicuro potenziato quantistica". Informazioni quantistiche. Calcola. 16, 61–86 (2016).

, Stefanie Barz, Vedran Dunjko, Florian Schlederer, Merritt Moore, Elham Kashefi e Ian A. Walmsley. "Calcolo delegato migliorato utilizzando la coerenza". Fis. Rev. A 93, 032339 (2016).
https: / / doi.org/ 10.1103 / PhysRevA.93.032339

, Marco Clementi, Anna Pappa, Andreas Eckstein, Ian A Walmsley, Elham Kashefi e Stefanie Barz. "Calcolo multipartitico classico utilizzando risorse quantistiche". Revisione fisica A 96, 062317 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.96.062317

, Nasir Ahmed e Kamisetty Ramamohan Rao. “Trasformata Walsh-Hadamard”. In Trasformate ortogonali per l'elaborazione del segnale digitale. Pagine 99–152. Springer (1975).

, Michael A Nielsen e Isaac L Chuang. "Calcolo quantistico e informazione quantistica: edizione per il decimo anniversario". Stampa dell'Università di Cambridge. (10).
https: / / doi.org/ 10.1017 / CBO9780511976667

, Philip Feinsilver e Jerzy Kocik. “Polinomi di Krawtchouk e matrici di Krawtchouk”. Pagine 115–141. Recenti progressi nella probabilità applicata. Springer negli Stati Uniti. Boston, MA (2005).
https://doi.org/10.1007/0-387-23394-6_5

, Philip Feinsilver e Rene Schott. "Trasformazioni e convoluzioni di Krawtchouk". Bollettino delle scienze matematichePagine 1–19 (2018).
https://doi.org/10.1007/s13373-018-0132-2

, M. Stobińska, A. Buraczewski, M. Moore, WR Clements, JJ Renema, SW Nam, T. Gerrits, A. Lita, WS Kolthammer, A. Eckstein e IA Walmsley. "L'interferenza quantistica consente l'elaborazione delle informazioni quantistiche in tempo costante". Progressi scientifici 5, eaau9674 (2019).
https:///doi.org/10.1126/sciadv.aau9674

, Ravindran Kannan e Achim Bachem. "Algoritmi polinomiali per il calcolo delle forme normali di Smith e Hermite di una matrice intera". SIAM Journal on Computing 8, 499–507 (1979).
https: / / doi.org/ 10.1137 / 0208040 mila

, Josh Alman e Virginia Vassilevska Williams. “Un metodo laser raffinato e una moltiplicazione della matrice più rapida”. In Atti del trentaduesimo simposio annuale ACM-SIAM sugli algoritmi discreti. Pagina 522–539. SODA'21USA (2021). Società per la matematica industriale e applicata.
https: / / doi.org/ 10.1137 / 1.9781611976465.32 mila

Citato da

Questo documento è pubblicato in Quantum sotto il Creative Commons Attribuzione 4.0 Internazionale (CC BY 4.0) licenza. Il copyright rimane dei detentori del copyright originali come gli autori o le loro istituzioni.