Patrick Rall
Quantum Information Center, University of Texas i Austin
Hitta det här uppsatsen intressant eller vill diskutera? Scite eller lämna en kommentar på SciRate.
Abstrakt
Vi överväger att utföra fasestimering under följande förhållanden: vi ges bara en kopia av ingångstillståndet, ingångstillståndet behöver inte vara en egen stat för enheten och staten får inte mätas. De flesta kvantestimeringsalgoritmer gör antaganden som gör dem olämpliga för denna "sammanhängande" inställning, och lämnar bara läroboksmetoden. Vi presenterar nya algoritmer för fas-, energi- och amplituduppskattning som är både konceptuellt och beräkningsmässigt enklare än läroboksmetoden, med både en mindre frågekomplexitet och tillhörande fotavtryck. De kräver inte en kvant Fourier -transform, och de kräver inte ett nätverk för kvantsortering för att beräkna medianen för flera uppskattningar. Istället använder de blockkodningstekniker för att beräkna uppskattningen en bit i taget, och utför all förstärkning via singulär värdetransformation. Dessa förbättrade underrutiner påskyndar prestanda för kvantmetropolprovtagning och Bayesiansk slutsats.
Utvalda bild: Vi presenterar en ny algoritm för energiskattning som beräknar uppskattningen en bit i taget. Varje bit extraheras via ett polynom som appliceras på Hamiltonian via singular value transformation. Bilden visar polynom approximationer av cosinus som efterbehandlas till ungefärliga kvadratiska vågor som anger bitarna.
Presentation på TQC 2021
Populär sammanfattning
► BibTeX-data
► Referenser
[1] Pawel Wocjan, Kristan Temme, Szegedy Walk Unitaries for 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-begränsad marktillståndsenergiuppskattning för tidiga feltoleranta kvantdatorer arXiv:2102.11340 (2021).
arXiv: 2102.11340
[4] Earl T. Campbell, Tidiga feltoleranta simuleringar av Hubbard-modellen arXiv:2012.09238 (2020).
arXiv: 2012.09238
[5] Yuan Su, Hsin-Yuan Huang, Earl T. Campbell, Nearly tight Trotterization of interacting electronics 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, Ett ramverk för att tillämpa kvantberäkning på icke-linjära dynamiska system 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-accelerated multilevel Monte Carlo-metoder för stokastiska differentialekvationer i matematisk finans arXiv:2012.06283 Quantum 5, 481 (2020).
https://doi.org/10.22331/q-2021-06-24-481
arXiv: 2012.06283
[8] Isaac Chuang, Stora enande av kvantalgoritmer. Seminariumpresentation på 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, Automatic Post-selection av Ancillae Thermalisation arXiv:2010.04173 Phys. Rev. Research 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, Enklare (klassisk) och snabbare (kvant) algoritmer för Gibbs partitionsfunktioner arXiv:2009.11270 (2020).
arXiv: 2009.11270
[11] András Gilyén, Zhao Song, Ewin Tang, En förbättrad kvantinspirerad algoritm för linjär regression 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 within 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 Algoritms for Estimating Physical Quantities using Block-Encodings Phys. Rev. A 102, 022408 arXiv:2004.06832 (2020).
https: / / doi.org/ 10.1103 / PhysRevA.102.022408
arXiv: 2004.06832
[14] Alessandro Roggero, spektral densitetsuppskattning med Gaussisk integraltransformfys. 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, Finding Angles for Quantum Signal Processing with Machine Precision arXiv:2003.02831 (2020).
https: / / doi.org/ 10.1145 / 3313276.3316366
arXiv: 2003.02831
[16] Lin Lin, Yu Tong, Nästan optimal marktillståndsberedning 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 for 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, Simplified Symposium on Simplicity in Algorithms. 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, Adaptiv kvantsimulerad glödgning för Bayesiansk inferens och uppskattning av partitionsfunktioner Proc. av SODA 2020 arXiv:1907.09965 (2019).
https: / / doi.org/ 10.1137 / 1.9781611975994.12
arXiv: 1907.09965
[22] Iordanis Kerenidis, Jonas Landman, Alessandro Luongo och Anupam Prakash, q-means: A quantum algorithm for unsupervised machine learning arXiv:1812.03584 NIPS 32 (2018).
arXiv: 1812.03584
[23] Yassine Hamoudi, Frédéric Magniez, Quantum Chebyshev's Inequality and Applications ICALP, LIPIcs Vol 132, sid 69:1-99:16 arXiv:1807.06456 (2018).
https: / / doi.org/ 10.4230 / LIPIcs.ICALP.2019.69
arXiv: 1807.06456
[24] Jeongwan Haah, Product Decomposition of Periodic Functions 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: exponential improvements for quantum matrix aritmetics arXiv:1806.01838 Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of 2019STOC193 (204STOC) –2018 (XNUMX).
arXiv: 1806.01838
[26] David Poulin, Alexei Kitaev, Damian S. Steiger, Matthew B. Hastings, Matthias Troyer, Quantum Algorithm for Spectral Measurement with Lower Gate Count arXiv:1711.11025 Phys. Rev. Lett. 121, 010501 (2017).
https: / / doi.org/ 10.1103 / PhysRevLett.121.010501
arXiv: 1711.11025
[27] Guang Hao Low, Isaac L. Chuang, Hamiltonian Simulation by Uniform Spectral Amplification arXiv:1707.05391 (2017).
arXiv: 1707.05391
[28] Iordanis Kerenidis, Anupam Prakash, Quantum gradient descent for linjära system och minsta kvadrater 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 of Hamiltonians och exponentiellt precisa mätningar Nature Communications volym 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, Hamiltonian Simulation by 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 by Quantum Signal Processing Phys. Rev. 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, sid. 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, Kvantalgoritm för system av linjära ekvationer med exponentiellt förbättrat beroende av precision SIAM Journal on Computing 46, 1920-1950 arXiv:1511.02306 (2015).
https: / / doi.org/ 10.1137 / 16M1087072
arXiv: 1511.02306
[34] Ashley Montanaro, Quantum speedup av Monte Carlo-metoder Proc. Roy. Soc. Ser. A, vol. 471 nr. 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, Robust Calibration of a Universal 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, Hamiltonsimulering med nästan optimalt beroende av alla parametrar arXiv:1501.01715 Proc. FOCS, s. 792-809 (2015).
https: / / doi.org/ 10.1109 / FOCS.2015.54
arXiv: 1501.01715
[37] Amnon Ta-Shma, Inverting well conditioned matrices in quantum logspace STOC '13, Pages 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 pages 290-308 (2011).
https: / / doi.org/ 10.1145 / 2493252.2493256
arXiv: 1103.2774
[40] Man-Hong Yung, Alán Aspuru-Guzik, A Quantum-Quantum Metropolis Algorithm arXiv:1011.1468 PNAS 109, 754-759 (2011).
https: / / doi.org/ 10.1073 / pnas.1111758109
arXiv: 1011.1468
[41] Andris Ambainis, Variabel tidsamplitudförstärkning och en snabbare kvantalgoritm för att lösa system av linjära ekvationer 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 volym 471, sidorna 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, sidorna 171–180 (2009).
arXiv: 0902.3757
[44] Aram W. Harrow, Avinatan Hassidim, Seth Lloyd, Kvantalgoritm för att lösa linjära ekvationssystem Phys. Rev. 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, Entanglement-free Heisenberg-limited phase estimering 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 speed-up of Markov-kedjebaserade algoritmer FOCS '04, sidorna 32-41 (2004).
https: / / doi.org/ 10.1109 / FOCS.2004.53
[48] Hartmut Klauck, Quantum Time-Space Tradeoffs for Sorting STOC 03, Pages 69–76 arXiv:quant-ph/0211174 (2002).
https: / / doi.org/ 10.1145 / 780542.780553
arXiv: kvant-ph / 0211174
[49] Peter Hoyer, Jan Neerbek, Yaoyun Shi, Quantum complexities of ordered searching, sorting, and element distinctness 28th ICALP, LNCS 2076, s. 346-357 arXiv:quant-ph/0102078 (2001).
https://doi.org/10.1007/3-540-48224-5_29
arXiv: kvant-ph / 0102078
[50] Isaac Chuang och Michael Nielsen, Quantum Computation and 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: kvant-ph / 0005055
[52] Dorit Aharonov, Alexei Kitaev, Noam Nisan, Quantum Circuits with Mixed States STOC '97, sid 20-30 arXiv:quant-ph/9806029 (1998).
https: / / doi.org/ 10.1145 / 276698.276708
arXiv: kvant-ph / 9806029
[53] Ashwin Nayak, Felix Wu, The quantum query complexity of approximation median och relaterad statistik arXiv:quant-ph/9804066 STOC '99 pp 384-393 (1998).
https: / / doi.org/ 10.1145 / 301250.301349
arXiv: kvant-ph / 9804066
[54] Charles H. Bennett, Ethan Bernstein, Gilles Brassard, Umesh Vazirani, Strengths and Weaknesses of Quantum Computing arXiv:quant-ph/9701001 SIAM Journal on Computing 26(5):1510-1523 (1997).
https: / / doi.org/ 10.1137 / S0097539796300933
arXiv: kvant-ph / 9701001
[55] A. Yu. Kitaev, Quantum measurements and the Abelian Stabilizer Problem arXiv:quant-ph/9511026 (1995).
arXiv: kvant-ph / 9511026
[56] Peter W. Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer SIAM J.Sci.Statist.Comput. 26, 1484 arXiv:quant-ph/9508027 (1995).
https: / / doi.org/ 10.1137 / S0097539795293172
arXiv: kvant-ph / 9508027
[57] Theodore J. Rivlin, An Introduction to the Approximation of Functions Dover Publications, Inc. New York. ISBN-13:978-0486640693 (1969).
Citerad av
[1] Yuan Su, Hsin-Yuan Huang och Earl T. Campbell, "Nästan tät traverisering av samverkande elektroner", arXiv: 2012.09194.
[2] John M. Martyn, Zane M. Rossi, Andrew K. Tan och Isaac L. Chuang, "A Grand Unification of Quantum Algorithms", arXiv: 2105.02859.
Ovanstående citat är från SAO / NASA ADS (senast uppdaterad framgångsrikt 2021-10-23 15:14:11). Listan kan vara ofullständig eftersom inte alla utgivare tillhandahåller lämpliga och fullständiga citatdata.
On Crossrefs citerade service Inga uppgifter om citerande verk hittades (sista försök 2021-10-23 15:14:09).
Detta papper publiceras i Quantum under Creative Commons Attribution 4.0 International (CC BY 4.0) licens. Upphovsrätten kvarstår med de ursprungliga upphovsrättsinnehavarna som författarna eller deras institutioner.
PlatoAi. Web3 Reimagined. Datainformation förstärkt.
Klicka här för att komma åt.
