Verbind je met ons

Plato verticaal zoeken

Quantum

Snellere coherente kwantumalgoritmen voor fase-, energie- en amplitudeschatting

Patrick Rall

Quantum Informatiecentrum, Universiteit van Texas in Austin

Vind je dit artikel interessant of wil je het bespreken? Scite of laat een reactie achter op SciRate.

Abstract

We overwegen faseschatting uit te voeren onder de volgende voorwaarden: we krijgen slechts één kopie van de invoertoestand, de invoertoestand hoeft geen eigentoestand van de unitaire te zijn en de toestand mag niet worden gemeten. De meeste algoritmen voor kwantumschatting maken aannames die ze ongeschikt maken voor deze 'coherente' instelling, waardoor alleen de leerboekbenadering overblijft. We presenteren nieuwe algoritmen voor fase-, energie- en amplitudeschatting die zowel conceptueel als rekenkundig eenvoudiger zijn dan de tekstboekmethode, met zowel een kleinere vraagcomplexiteit als een bijkomende voetafdruk. Ze hebben geen kwantum Fourier-transformatie nodig en ze hebben geen kwantumsorteernetwerk nodig om de mediaan van verschillende schattingen te berekenen. In plaats daarvan gebruiken ze blokcoderingstechnieken om de schatting bit voor bit te berekenen, waarbij ze alle versterking uitvoeren via singuliere waardetransformatie. Deze verbeterde subroutines versnellen de prestaties van kwantummetropolis-bemonstering en kwantum Bayesiaanse inferentie.


Presentatie op TQC 2021

Een fundamenteel doel van kwantumcomputing is om fysieke systemen te helpen bestuderen. Een van de eerste resultaten op dit gebied was een snel kwantumalgoritme voor het meten van de energie van een systeem, dat als bouwsteen kan dienen voor andere kwantumalgoritmen. Dit algoritme is echter erg ingewikkeld en moeilijk te analyseren. In dit artikel presenteren we een eenvoudigere methode gebaseerd op het toepassen van polynomen op de Hamiltoniaan die elk van de bits van de schatting extraheren. Deze techniek is tot 20x sneller dan de stand van de techniek.

► BibTeX-gegevens

► Referenties

[1] Pawel Wocjan, Kristan Temme, Szegedy Walk Unitaries voor Quantum Maps arXiv: 2107.07365 (2021).
arXiv: 2107.07365

[2] John M. Martyn, Zane M. Rossi, Andrew K. Tan, Isaac L. Chuang, A Grand Unification of Quantum Algorithms arXiv:2105.02859 (2021).
arXiv: 2105.02859

[3] Lin Lin, Yu Tong, Heisenberg-beperkte schatting van de grondtoestandsenergie voor vroege fouttolerante kwantumcomputers arXiv:2102.11340 (2021).
arXiv: 2102.11340

Advertentie. Scroll om verder te lezen.

[4] Earl T. Campbell, vroege fouttolerante simulaties van het Hubbard-model arXiv:2012.09238 (2020).
arXiv: 2012.09238

[5] Yuan Su, Hsin-Yuan Huang, Earl T. Campbell, bijna strakke Trotterisatie van op elkaar inwerkende elektronen arXiv:2012.09194 Quantum 5, 495 (2020).
https:/​/​doi.org/​10.22331/​q-2021-07-05-495
arXiv: 2012.09194

[6] Alexander Engel, Graeme Smith, Scott E. Parker, Een raamwerk voor het toepassen van kwantumberekening op niet-lineaire dynamische systemen arXiv:2012.06681 Physics of Plasmas 28, 062305 (2020).
https: / / doi.org/ 10.1063 / 5.0040313
arXiv: 2012.06681

[7] Dong An, Noah Linden, Jin-Peng Liu, Ashley Montanaro, Changpeng Shao, Jiasu Wang, Quantum-versnelde Monte Carlo-methoden op meerdere niveaus voor stochastische differentiaalvergelijkingen in wiskundige financiën arXiv:2012.06283 Quantum 5, 481 (2020).
https:/​/​doi.org/​10.22331/​q-2021-06-24-481
arXiv: 2012.06283

[8] Isaac Chuang, Grote eenwording van kwantumalgoritmen. Seminarpresentatie bij IQC Waterloo. (2020).
https:/​/​uwaterloo.ca/​institute-for-quantum-computing/​events/​grand-unification-quantum-algorithms

[9] Lewis Wright, Fergus Barratt, James Dborin, George H. Booth, Andrew G. Green, automatische naselectie door Ancillae Thermalisation arXiv:2010.04173 Phys. Rev. Onderzoek 3, 033151 (2020).
https: / / doi.org/ 10.1103 / PhysRevResearch.3.033151
arXiv: 2010.04173

[10] Srinivasan Arunachalam, Vojtech Havlicek, Giacomo Nannicini, Kristan Temme, Pawel Wocjan, eenvoudiger (klassiek) en sneller (kwantum) algoritmen voor Gibbs-partitiefuncties arXiv:2009.11270 (2020).
arXiv: 2009.11270

[11] András Gilyén, Zhao Song, Ewin Tang, een verbeterd op kwantum geïnspireerd algoritme voor lineaire regressie arXiv:2009.07268 (2020).
arXiv: 2009.07268

[12] Phillip WK Jensen, Lasse Bjørn Kristensen, Jakob S. Kottmann, Alán Aspuru-Guzik, Quantum Computation of eigenvalues ​​binnen Target Intervals Quantum Science and Technology 6, 015004 arXiv:2005.13434 (2020).
https:/​/​doi.org/​10.1088/​2058-9565/​abc096
arXiv: 2005.13434

[13] Patrick Rall, Quantum Algoritmes voor het schatten van fysieke hoeveelheden met behulp van Block-Encodings Phys. Rev. A 102, 022408 arXiv:2004.06832 (2020).
https: / / doi.org/ 10.1103 / PhysRevA.102.022408
arXiv: 2004.06832

Advertentie. Scroll om verder te lezen.

[14] Alessandro Roggero, Spectrale dichtheidsschatting met de Gaussiaanse Integrale Transformatie Phys. Rev. A 102, 022409 arXiv:2004.04889 (2020).
https: / / doi.org/ 10.1103 / PhysRevA.102.022409
arXiv: 2004.04889

[15] Rui Chao, Dawei Ding, Andras Gilyen, Cupjin Huang, Mario Szegedy, Hoeken vinden voor kwantumsignaalverwerking met machineprecisie arXiv: 2003.02831 (2020).
https: / / doi.org/ 10.1145 / 3313276.3316366
arXiv: 2003.02831

[16] Lin Lin, Yu Tong, Bijna optimale voorbereiding van de grondtoestand arXiv: 2002.12508 Quantum 4, 372 (2020).
https:/​/​doi.org/​10.22331/​q-2020-12-14-372
arXiv: 2002.12508

[17] Andrew M. Childs, Yuan Su, Minh C. Tran, Nathan Wiebe, Shuchen Zhu, A Theory of Trotter Error Phys. Rev. X 11, 011020 arXiv:1912.08854 (2019).
https: / / doi.org/ 10.1103 / PhysRevX.11.011020
arXiv: 1912.08854

[18] Dmitry Grinko, Julien Gacon, Christa Zoufal, Stefan Woerner, Iterative Quantum Amplitude Estimation npj Quantum Inf 7, 52 arXiv: 1912.05559 (2019).
https:/​/​doi.org/​10.1038/​s41534-021-00379-1
arXiv: 1912.05559

[19] Jessica Lemieux, Bettina Heim, David Poulin, Krysta Svore, Matthias Troyer, Efficient Quantum Walk Circuits voor Metropolis-Hastings Algorithm Quantum 4, 287 arXiv:1910.01659 (2019).
https:/​/​doi.org/​10.22331/​q-2020-06-29-287
arXiv: 1910.01659

[20] Scott Aaronson, Patrick Rall, Quantum Approximate Counting, vereenvoudigd symposium over eenvoud in algoritmen. 2020, 24-32 arXiv:1908.10846(2019).
https: / / doi.org/ 10.1137 / 1.9781611976014.5
arXiv: 1908.10846

[21] Aram W. Harrow, Annie Y. Wei, Adaptive Quantum Simulated Annealing voor Bayesiaanse inferentie en schatting van partitiefuncties Proc. van SODA 2020 arXiv:1907.09965 (2019).
https: / / doi.org/ 10.1137 / 1.9781611975994.12
arXiv: 1907.09965

[22] Iordanis Kerenidis, Jonas Landman, Alessandro Luongo en Anupam Prakash, q-means: een kwantumalgoritme voor machinaal leren zonder toezicht arXiv: 1812.03584 NIPS 32 (2018).
arXiv: 1812.03584

[23] Yassine Hamoudi, Frédéric Magniez, Quantum Chebyshev's ongelijkheid en toepassingen ICALP, LIPIcs Vol 132, pagina's 69: 1-99: 16 arXiv: 1807.06456 (2018).
https: / / doi.org/ 10.4230 / LIPIcs.ICALP.2019.69
arXiv: 1807.06456

Advertentie. Scroll om verder te lezen.

[24] Jeongwan Haah, Productdecompositie van periodieke functies in Quantum Signal Processing Quantum 3, 190. arXiv:1806.10236 (2018).
https:/​/​doi.org/​10.22331/​q-2019-10-07-190
arXiv: 1806.10236

[25] András Gilyén, Yuan Su, Guang Hao Low, Nathan Wiebe, Quantum singular value transformation and beyond: exponentiële verbeteringen voor kwantummatrix-rekenkunde arXiv:1806.01838 Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC 2019) Pagina's 193-204 ( 2018).
arXiv: 1806.01838

[26] David Poulin, Alexei Kitaev, Damian S. Steiger, Matthew B. Hastings, Matthias Troyer, kwantumalgoritme voor spectrale meting met lagere poorttelling arXiv:1711.11025 Phys. ds. Lett. 121, 010501 (2017).
https: / / doi.org/ 10.1103 / PhysRevLett.121.010501
arXiv: 1711.11025

[27] Guang Hao Low, Isaac L. Chuang, Hamiltoniaanse simulatie door uniforme spectrale versterking arXiv: 1707.05391 (2017).
arXiv: 1707.05391

[28] Iordanis Kerenidis, Anupam Prakash, Quantum gradiënt afdaling voor lineaire systemen en kleinste kwadraten arXiv:1704.04992 Phys. Rev. A 101, 022316 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.101.022316
arXiv: 1704.04992

[29] Yosi Atia, Dorit Aharonov, Fast-forwarding van Hamiltonians en exponentieel nauwkeurige metingen Nature Communications volume 8, 1572 arXiv: 1610.09619 (2016).
https:/​/​doi.org/​10.1038/​s41467-017-01637-7
arXiv: 1610.09619

[30] Guang Hao Low, Isaac L. Chuang, Hamiltoniaanse simulatie door Qubitization Quantum 3, 163 arXiv: 1610.06546 (2016).
https:/​/​doi.org/​10.22331/​q-2019-07-12-163
arXiv: 1610.06546

[31] Guang Hao Low, Isaac L. Chuang, Optimal Hamiltonian Simulation door Quantum Signal Processing Phys. ds. Lett. 118, 010501 arXiv:1606.02685 (2016).
https: / / doi.org/ 10.1103 / PhysRevLett.118.010501
arXiv: 1606.02685

[32] Iordanis Kerenidis, Anupam Prakash, Quantum Recommendation Systems arXiv:1603.08675 ITCS 2017, p. 49: 1-49: 21 (2016).
https: / / doi.org/ 10.4230 / LIPIcs.ITCS.2017.49
arXiv: 1603.08675

[33] Andrew M. Childs, Robin Kothari, Rolando D. Somma, Quantum-algoritme voor systemen van lineaire vergelijkingen met exponentieel verbeterde afhankelijkheid van precisie SIAM Journal on Computing 46, 1920-1950 arXiv: 1511.02306 (2015).
https: / / doi.org/ 10.1137 / 16M1087072
arXiv: 1511.02306

Advertentie. Scroll om verder te lezen.

[34] Ashley Montanaro, Quantumversnelling van Monte Carlo-methoden Proc. Roy. Soc. ser. A, vol. 471 nee. 2181, 20150301 arXiv:1504.06987 (2015).
https: / / doi.org/ 10.1098 / rspa.2015.0301
arXiv: 1504.06987

[35] Shelby Kimmel, Guang Hao Low, Theodore J. Yoder, Robuuste kalibratie van een universele Single-Qubit Gate-Set via Robust Phase Estimation Phys. Rev. A 92, 062315 arXiv:1502.02677 (2015).
https: / / doi.org/ 10.1103 / PhysRevA.92.062315
arXiv: 1502.02677

[36] Dominic W. Berry, Andrew M. Childs, Robin Kothari, Hamiltoniaanse simulatie met bijna optimale afhankelijkheid van alle parameters arXiv:1501.01715 Proc. FOCS, blz. 792-809 (2015).
https: / / doi.org/ 10.1109 / FOCS.2015.54
arXiv: 1501.01715

[37] Amnon Ta-Shma, omkeren van goed geconditioneerde matrices in kwantumlogspace STOC '13, pagina's 881-890 (2013).
https: / / doi.org/ 10.1145 / 2488608.2488720

[38] Robert Beals, Stephen Brierley, Oliver Gray, Aram Harrow, Samuel Kutin, Noah Linden, Dan Shepherd, Mark Stather, Efficient Distributed Quantum Computing Proc. R. Soc. A 2013 469, 20120686 arXiv: 1207.2307 (2012).
https: / / doi.org/ 10.1098 / rspa.2012.0686
arXiv: 1207.2307

[39] Maris Ozols, Martin Roetteler, Jérémie Roland, Quantum Rejection Sampling arXiv: 1103.2774 IRCS'12 pagina's 290-308 (2011).
https: / / doi.org/ 10.1145 / 2493252.2493256
arXiv: 1103.2774

[40] Man-Hong Yung, Alan Aspuru-Guzik, een Quantum-Quantum Metropolis-algoritme arXiv: 1011.1468 PNAS 109, 754-759 (2011).
https: / / doi.org/ 10.1073 / pnas.1111758109
arXiv: 1011.1468

[41] Andris Ambainis, Variabele tijdamplitudeversterking en een sneller kwantumalgoritme voor het oplossen van stelsels van lineaire vergelijkingen arXiv: 1010.4458 STACS'12, 636-647 (2010).
https: / / doi.org/ 10.4230 / LIPIcs.STACS.2012.636
arXiv: 1010.4458

[42] K. Temme, TJ Osborne, KG Vollbrecht, D. Poulin, F. Verstraete, Quantum Metropolis Sampling arXiv:0911.3635 Nature volume 471, pagina's 87-90 (2009).
https: / / doi.org/ 10.1038 / nature09770
arXiv: 0911.3635

[43] Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, Rocco Servedio, Emanuele Viola, Bounded Independence Fools Halfspaces arXiv:0902.3757 FOCS '09, pagina's 171-180 (2009).
arXiv: 0902.3757

Advertentie. Scroll om verder te lezen.

[44] Aram W. Harrow, Avinatan Hassidim, Seth Lloyd, Quantum-algoritme voor het oplossen van lineaire stelsels van vergelijkingen Phys. ds. Lett. 103, 150502 arXiv:0811.3171 (2008).
https: / / doi.org/ 10.1103 / PhysRevLett.103.150502
arXiv: 0811.3171

[45] BL Higgins, DW Berry, SD Bartlett, HM Wiseman, GJ Pryde, verstrengelingsvrije Heisenberg-beperkte faseschatting Nature.450:393-396 arXiv:0709.2996 (2007).
https: / / doi.org/ 10.1038 / nature06257
arXiv: 0709.2996

[46] Chris Marriott, John Watrous, Quantum Arthur-Merlin Games CC, 14 (2): 122 – 152 arXiv:cs/​0506068 (2005).
https: / / doi.org/ 10.1007 / s00037-005-0194-x
arXiv: cs / 0506068

[47] Mario Szegedy, Quantum-versnelling van Markov-ketengebaseerde algoritmen FOCS '04, pagina's 32-41 (2004).
https: / / doi.org/ 10.1109 / FOCS.2004.53

[48] Hartmut Klauck, Quantum tijd-ruimte compromissen voor het sorteren van STOC 03, pagina's 69-76 arXiv:quant-ph/​0211174 (2002).
https: / / doi.org/ 10.1145 / 780542.780553
arXiv: quant-ph / 0211174

[49] Peter Hoyer, Jan Neerbek, Yaoyun Shi, Quantum complexiteiten van geordend zoeken, sorteren en onderscheiden van elementen 28e ICALP, LNCS 2076, blz. 346-357 arXiv:quant-ph/0102078 (2001).
https:/​/​doi.org/​10.1007/​3-540-48224-5_29
arXiv: quant-ph / 0102078

[50] Isaac Chuang en Michael Nielsen, Quantum Computation en Quantum Information Cambridge University Press. ISBN-13: 978-1107002173 (2000).

[51] Gilles Brassard, Peter Hoyer, Michele Mosca, Alain Tapp, Quantum Amplitude Amplification and Estimation Quantum Computation and Quantum Information, 305:53-74 arXiv:quant-ph/​0005055 (2000).
https: / / doi.org/ 10.1090 / conm / 305 / 05215
arXiv: quant-ph / 0005055

[52] Dorit Aharonov, Alexei Kitaev, Noam Nisan, Quantum Circuits with Mixed States STOC '97, pagina's 20-30 arXiv:quant-ph/​9806029 (1998).
https: / / doi.org/ 10.1145 / 276698.276708
arXiv: quant-ph / 9806029

[53] Ashwin Nayak, Felix Wu, De kwantumquery-complexiteit van het benaderen van de mediaan en gerelateerde statistieken arXiv:quant-ph/​9804066 STOC '99 pp 384-393 (1998).
https: / / doi.org/ 10.1145 / 301250.301349
arXiv: quant-ph / 9804066

Advertentie. Scroll om verder te lezen.

[54] Charles H. Bennett, Ethan Bernstein, Gilles Brassard, Umesh Vazirani, Sterke en zwakke punten van Quantum Computing arXiv:quant-ph/​9701001 SIAM Journal on Computing 26(5):1510-1523 (1997).
https: / / doi.org/ 10.1137 / S0097539796300933
arXiv: quant-ph / 9701001

[55] A. Yu. Kitaev, Quantummetingen en het Abelian Stabilizer Problem arXiv:quant-ph/​9511026 (1995).
arXiv: quant-ph / 9511026

[56] Peter W. Shor, polynomiale tijdalgoritmen voor priemfactorisatie en discrete logaritmen op een kwantumcomputer SIAM J.Sci.Statist.Comput. 26, 1484 arXiv:quant-ph/​9508027 (1995).
https: / / doi.org/ 10.1137 / S0097539795293172
arXiv: quant-ph / 9508027

[57] Theodore J. Rivlin, een inleiding tot de aanpassing van functies Dover Publications, Inc. New York. ISBN-13:978-0486640693 (1969).

Geciteerd door

[1] Yuan Su, Hsin-Yuan Huang en Earl T. Campbell, "Bijna strakke dravering van op elkaar inwerkende elektronen", arXiv: 2012.09194.

[2] John M. Martyn, Zane M. Rossi, Andrew K. Tan en Isaac L. Chuang, "Een grote unificatie van kwantumalgoritmen", arXiv: 2105.02859.

Bovenstaande citaten zijn afkomstig van SAO / NASA ADS (laatst bijgewerkt met succes 2021-10-23 15:14:11). De lijst is mogelijk onvolledig omdat niet alle uitgevers geschikte en volledige citatiegegevens verstrekken.

On De door Crossref geciteerde service er zijn geen gegevens gevonden over het citeren van werken (laatste poging 2021-10-23 15:14:09).

PlatoAi. Web3 opnieuw uitgevonden. Gegevensintelligentie versterkt.
Klik hier om toegang te krijgen.

Advertentie. Scroll om verder te lezen.

Bron: https://quantum-journal.org/papers/q-2021-10-19-566/

Geschreven Door

advertentie

Gerelateerde streams

Blockchain

Ondanks de risico's bij het gebruik van cryptocurrencies en de stappen om de controle over cryptocurrencies door de regeringen aan te scherpen, worden cryptocurrencies tegenwoordig steeds meer...

Blockchain

MyTona is het eerste bedrijf in Rusland dat zijn plannen in de Metaverse-sector aankondigt. De in Yakutsk gevestigde game-ontwikkelaar zei in een release ...

Blockchain

ELON en zijn astronomische stijgingen zijn er altijd in geslaagd om mensen uit de crypto-ruimte te verbazen. Zo registreerde de genoemde munt vrij recent een enorme...

Blockchain

Play-to-earn gamingplatform Axie Infinity heeft onlangs op Twitter gepost dat "A Genesis Land Plot zojuist is verkocht voor 550 ETH." Voor een bedrag van 2.3 miljoen dollar...