Λογότυπο Zephyrnet

Ταχύτεροι συνεκτικοί κβαντικοί αλγόριθμοι για εκτίμηση φάσης, ενέργειας και πλάτους

Ημερομηνία:

Πάτρικ Ραλ

Κβαντικό Κέντρο Πληροφοριών, Πανεπιστήμιο του Τέξας στο Ώστιν

Βρείτε αυτό το άρθρο ενδιαφέρουσα ή θέλετε να συζητήσετε; Scite ή αφήστε ένα σχόλιο για το SciRate.

Περίληψη

Εξετάζουμε την εκτίμηση φάσης υπό τις ακόλουθες συνθήκες: μας δίνεται μόνο ένα αντίγραφο της κατάστασης εισόδου, η κατάσταση εισόδου δεν χρειάζεται να είναι ιδιοκατάσταση της ενιαίας και η κατάσταση δεν πρέπει να μετρηθεί. Οι περισσότεροι αλγόριθμοι κβαντικής εκτίμησης κάνουν υποθέσεις που τους καθιστούν ακατάλληλους για αυτή τη «συνεκτική» ρύθμιση, αφήνοντας μόνο την προσέγγιση του σχολικού βιβλίου. Παρουσιάζουμε καινοτόμους αλγόριθμους για εκτίμηση φάσης, ενέργειας και πλάτους που είναι τόσο εννοιολογικά όσο και υπολογιστικά απλούστεροι από τη μέθοδο του σχολικού βιβλίου, με μικρότερη πολυπλοκότητα ερωτήματος και μικρότερο αποτύπωμα. Δεν απαιτούν κβαντικό μετασχηματισμό Fourier και δεν απαιτούν κβαντικό δίκτυο διαλογής για τον υπολογισμό του μέσου όρου πολλών εκτιμήσεων. Αντ 'αυτού, χρησιμοποιούν τεχνικές κωδικοποίησης μπλοκ για να υπολογίσουν την εκτίμηση ένα bit κάθε φορά, εκτελώντας όλη την ενίσχυση μέσω μετασχηματισμού μοναδικής αξίας. Αυτές οι βελτιωμένες υπορουτίνες επιταχύνουν την απόδοση της κβαντικής δειγματοληψίας Metropolis και της κβαντικής συμπερασματικότητας Bayesian.


Παρουσίαση στο TQC 2021

Ένας θεμελιώδης στόχος των κβαντικών υπολογιστών είναι να βοηθήσει στη μελέτη φυσικών συστημάτων. Ένα από τα πρώτα αποτελέσματα στην περιοχή ήταν ένας γρήγορος κβαντικός αλγόριθμος για τη μέτρηση της ενέργειας ενός συστήματος, ο οποίος μπορεί να χρησιμεύσει ως δομικό στοιχείο για άλλους κβαντικούς αλγόριθμους. Ωστόσο, αυτός ο αλγόριθμος είναι πολύ περίπλοκος και δύσκολο να αναλυθεί. Σε αυτή την εργασία παρουσιάζουμε μια απλούστερη μέθοδο που βασίζεται στην εφαρμογή πολυωνύμων στο Hamiltonian που εξάγουν κάθε ένα από τα bit της εκτίμησης. Αυτή η τεχνική είναι έως και 20 φορές ταχύτερη από την προηγούμενη κατάσταση της τέχνης.

► Δεδομένα BibTeX

► Αναφορές

[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-περιορισμένη εκτίμηση της βασικής κατάστασης ενέργειας για πρώιμους ανεκτικούς σε σφάλματα κβαντικούς υπολογιστές arXiv:2102.11340 (2021).
arXiv: 2102.11340

[4] Earl T. Campbell, Early fault-tolerant προσομοιώσεις του μοντέλου Hubbard arXiv:2012.09238 (2020).
arXiv: 2012.09238

[5] Yuan Su, Hsin-Yuan Huang, Earl T. Campbell, Nearly tight Trotterization of interacting electrons 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, Ένα πλαίσιο για την εφαρμογή του κβαντικού υπολογισμού σε μη γραμμικά δυναμικά συστήματα 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, Κβαντικές επιταχυνόμενες πολυεπίπεδες μέθοδοι Monte Carlo για στοχαστικές διαφορικές εξισώσεις στη μαθηματική χρηματοοικονομική arXiv:2012.06283 Quantum 5, 481.
https:/​/​doi.org/​10.22331/​q-2021-06-24-481
arXiv: 2012.06283

[8] Isaac Chuang, Μεγάλη ενοποίηση κβαντικών αλγορίθμων. Παρουσίαση σεμιναρίου στο 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 by 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, Απλούστεροι (κλασικοί) και ταχύτεροι (κβαντικοί) αλγόριθμοι για συναρτήσεις διαμερίσματος Gibbs arXiv:2009.11270 (2020).
arXiv: 2009.11270

[11] András Gilyén, Zhao Song, Ewin Tang, Ένας βελτιωμένος αλγόριθμος εμπνευσμένος από κβάντα για γραμμική παλινδρόμηση 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 ​​into 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, Κβαντικοί αλγόριθμοι για την εκτίμηση φυσικών μεγεθών με χρήση κωδικοποιήσεων μπλοκ Phys. Αναθ. A 102, 022408 arXiv:2004.06832 (2020).
https: / / doi.org/ 10.1103 / PhysRevA.102.022408
arXiv: 2004.06832

[14] Alessandro Roggero, Εκτίμηση φασματικής πυκνότητας με το Gaussian Integral Transform Phys. Αναθ. 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, Σχεδόν βέλτιστη προετοιμασία βασικής κατάστασης 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. Αναθ. 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, Απλοποιημένο Συμπόσιο για την Απλότητα στους Αλγόριθμους. 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 for Bayesian Inference and Estimating Partition Functions Proc. του SODA 2020 arXiv:1907.09965 (2019).
https: / / doi.org/ 10.1137 / 1.9781611975994.12
arXiv: 1907.09965

[22] Ιορδάνης Κερενίδης, Jonas Landman, Alessandro Luongo και 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, σελίδες 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, Κβαντικός μετασχηματισμός μοναδικής τιμής και πέρα: εκθετικές βελτιώσεις για την αριθμητική κβαντικής μήτρας arXiv:1806.01838 Πρακτικά του 51ου Ετήσιου Συμπόσιου ACM SIGACT (Σελίδα 2019ST) SIGACT (Σελίδα 193ΣΤ204) –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. Αναθ. 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] Ιορδάνης Κερενίδης, Anupam Prakash, Quantum gradient descent for γραμμικά συστήματα και ελάχιστα τετράγωνα arXiv:1704.04992 Φυσ. Α' 101, 022316 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.101.022316
arXiv: 1704.04992

[29] Yosi Atia, Dorit Aharonov, Fast-forwarding of Hamiltonians and exponentially ακριβείς μετρήσεις Nature Communications τόμος 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. Αναθ. Lett. 118, 010501 arXiv:1606.02685 (2016).
https: / / doi.org/ 10.1103 / PhysRevLett.118.010501
arXiv: 1606.02685

[32] Ιορδάνης Κερενίδης, Anupam Prakash, Quantum Recommendation Systems arXiv:1603.08675 ITCS 2017, σελ. 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, Κβαντικός αλγόριθμος για συστήματα γραμμικών εξισώσεων με εκθετικά βελτιωμένη εξάρτηση από την ακρίβεια SIAM Journal on Computing 46, 1920-1950 arXiv:1511.02306 (2015).
https: / / doi.org/ 10.1137 / 16M1087072
arXiv: 1511.02306

[34] Ashley Montanaro, Κβαντική επιτάχυνση των μεθόδων Monte Carlo Proc. Ρόι. Soc. Ser. Α, τόμ. 471 αρ. 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. Αναθ. Α 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, Hamiltonian simulation με σχεδόν βέλτιστη εξάρτηση από όλες τις παραμέτρους arXiv:1501.01715 Proc. FOCS, σελ. 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, Σελίδες 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 σελίδες 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, Variable time amplitude amplification and a faster quantum algorithm for solving systems of linear equations 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 τόμος 471, σελίδες 87–90 (2009).
https: / / doi.org/ 10.1038 / nature09770
arXiv: 0911.3635

[43] Ηλίας Διακονικόλας, Parikshit Gopalan, Ragesh Jaiswal, Rocco Servedio, Emanuele Viola, Bounded Independence Fools Halfspaces arXiv:0902.3757 FOCS '09, Σελίδες 171–180 (2009).
arXiv: 0902.3757

[44] Aram W. Harrow, Avinatan Hassidim, Seth Lloyd, Quantum algorithm for solving linear systems of equations Phys. Αναθ. 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, Εκτίμηση φάσης περιορισμένης από εμπλοκή Heisenberg χωρίς εμπλοκή 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, Κβαντική επιτάχυνση αλγορίθμων που βασίζονται στην αλυσίδα Markov FOCS '04, Σελίδες 32-41 (2004).
https: / / doi.org/ 10.1109 / FOCS.2004.53

[48] ​​Hartmut Klauck, Quantum Time-Space Tradeoffs for Sorting STOC 03, Σελίδες 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 complexities of ordered searching, sorting, and element distinctness 28th ICALP, LNCS 2076, σελ. 346-357 arXiv:quant-ph/​0102078 (2001).
https:/​/​doi.org/​10.1007/​3-540-48224-5_29
arXiv: quant-ph / 0102078

[50] Isaac Chuang και 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: quant-ph / 0005055

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

[53] Ashwin Nayak, Felix Wu, Η πολυπλοκότητα του κβαντικού ερωτήματος της προσέγγισης της διάμεσης και των σχετικών στατιστικών arXiv:quant-ph/​9804066 STOC '99 σελ. 384-393 (1998).
https: / / doi.org/ 10.1145 / 301250.301349
arXiv: quant-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: quant-ph / 9701001

[55] A. Yu. Kitaev, Κβαντικές μετρήσεις και Πρόβλημα Abelian Stabilizer arXiv:quant-ph/​9511026 (1995).
arXiv: quant-ph / 9511026

[56] Peter W. Shor, Πολυωνυμικοί αλγόριθμοι χρόνου για πρωταρχική παραγοντοποίηση και διακριτοί λογάριθμοι σε κβαντικό υπολογιστή 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, An Introduction to the Approximation of Functions Publications Dover, Inc. Νέα Υόρκη. ISBN-13:978-0486640693 (1969).

Αναφέρεται από

[1] Yuan Su, Hsin-Yuan Huang, και Earl T. Campbell, "Σχεδόν σφιχτό τροτερισμό των αλληλεπιδρώντων ηλεκτρονίων", arXiv: 2012.09194.

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

Οι παραπάνω αναφορές είναι από SAO / NASA ADS (τελευταία ενημέρωση επιτυχώς 2021-10-23 15:14:11). Η λίστα μπορεί να είναι ελλιπής, καθώς δεν παρέχουν όλοι οι εκδότες τα κατάλληλα και πλήρη στοιχεία αναφοράς.

On Η υπηρεσία παραπομπής του Crossref δεν βρέθηκαν δεδομένα σχετικά με την αναφορά έργων (τελευταία προσπάθεια 2021-10-23 15:14:09).

Πλάτωνας. Επανεκτίμησε το Web3. Ενισχυμένη ευφυΐα δεδομένων.
Κάντε κλικ εδώ για πρόσβαση.

Πηγή: https://quantum-journal.org/papers/q-2021-10-19-566/

spot_img

Τελευταία Νοημοσύνη

spot_img