Kortare kvantkretsar via enkel-qubit-grindapproximation

Kortare kvantkretsar via enkel-qubit-grindapproximation

Tidsstämpel: 18 december 2023 8:56
Kortare kvantkretsar via enkel-qubit-grindapproximation PlatoBlockchain Data Intelligence. Vertikal sökning. Ai.

Vadym Kliuchnikov1,2, Kristin Lauter3, Romy Minko4,5, Adam Paetznick1, och Christophe Petit6,7

1Microsoft Quantum, Redmond, WA, USA
2Microsoft Quantum, Toronto, ON, CA
3Facebook AI Research, Seattle, WA, USA
4University of Oxford, Oxford, Storbritannien
5Heilbronn Institute for Mathematical Research, University of Bristol, Bristol, Storbritannien
6University of Birmingham, Birmingham, Storbritannien
7Université Libre de Bruxelles, Bryssel, Belgien

Hitta det här uppsatsen intressant eller vill diskutera? Scite eller lämna en kommentar på SciRate.

Abstrakt

Vi ger en ny procedur för att approximera allmänna enkel-qubit-enheter från en finit universell grinduppsättning genom att reducera problemet till ett nytt magnitudapproximationsproblem, vilket uppnår en omedelbar förbättring av sekvenslängden med en faktor 7/9. Förlängning av arbetet [28] Och [15], visar vi att att ta sannolikhetsblandningar av kanaler för att lösa fallback [13] och magnitud approximationsproblem sparar faktor två i approximationskostnader. Speciellt, över Clifford+$sqrt{mathrm{T}}$ gate set uppnår vi ett genomsnittligt antal icke-Clifford gate på $0.23log_2(1/varepsilon)+2.13$ och T-count $0.56log_2(1/varepsilon)+5.3 $ med blandade reservuppskattningar för diamantnormnoggrannhet $varepsilon$.
Detta dokument ger en holistisk översikt av gate approximation, utöver dessa nya insikter. Vi ger en heltäckande procedur för grindapproximation för generella grinduppsättningar relaterade till vissa kvartjonalgebror, och ger pedagogiska exempel med vanliga feltoleranta grinduppsättningar (V, Clifford+T och Clifford+$sqrt{mathrm{T}}$) . Vi tillhandahåller även detaljerade numeriska resultat för Clifford+T och Clifford+$sqrt{mathrm{T}}$ gate set. I ett försök att hålla tidningen fristående inkluderar vi en översikt över relevanta algoritmer för heltalspunktsuppräkning och relativ normekvationslösning. Vi tillhandahåller ett antal ytterligare tillämpningar av storleksuppskattningsproblemen, såväl som förbättrade algoritmer för exakt syntes, i bilagorna.

► BibTeX-data

► Referenser

[1] Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C. Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando GSL Brandao, David A. Buell, Brian Burkett, Yu Chen, Zijun Chen, Ben Chiaro, Roberto Collins, William Courtney, Andrew Dunsworth, Edward Farhi, Brooks Foxen, Austin Fowler, Craig Gidney, Marissa Giustina, Rob Graff, Keith Guerin, Steve Habegger, Matthew P. Harrigan, Michael J. Hartmann, Alan Ho, Markus Hoffmann, Trent Huang, Travis S. Humble, Sergei V. Isakov, Evan Jeffrey, Zhang Jiang, Dvir Kafri, Kostyantyn Kechedzhi, Julian Kelly, Paul V. Klimov, Sergey Knysh, Alexander Korotkov, Fedor Kostritsa, David Landhuis, Mike Lindmark, Erik Lucero, Dmitry Lyakh, Salvatore Mandrà, Jarrod R. McClean, Matthew McEwen, Anthony Megrant, Xiao Mi, Kristel Michielsen, Masoud Mohseni, Josh Mutus, Ofer Naaman, Matthew Neeley, Charles Neill, Murphy Yuezhen Niu, Eric Ostby, Andre Petukhov, John C. Platt, Chris Quintana, Eleanor G. Rieffel, Pedram Roushan, Nicholas C. Rubin, Daniel Sank, Kevin J. Satzinger, Vadim Smelyanskiy, Kevin J. Sung, Matthew D. Trevithick, Amit Vainsencher, Benjamin Villalonga, Theodore White, Z. Jamie Yao , Ping Yeh, Adam Zalcman, Hartmut Neven och John M. Martinis, "Quantum supremacy using a programmerbar supraconducting processor" Nature 574, 505-510 (2019).
https:/​/​doi.org/​10.1038/​s41586-019-1666-5

[2] Wojciech Banaszczyk "Ojämlikheter för konvexa kroppar och polära reciproka gitter i $R^n$" Discrete & Computational Geometry 13, 217–231 (1995).
https: / / doi.org/ 10.1007 / BF02574039

[3] Adriano Barenco, Charles H. Bennett, Richard Cleve, David P. DiVincenzo, Norman Margolus, Peter Shor, Tycho Sleator, John A. Smolin och Harald Weinfurter, "Elementary gates for quantum computing" Physical Review A 52, 3457–3467 ( 1995).
https: / / doi.org/ 10.1103 / PhysRevA.52.3457

[4] Andreas Blass, Alex Bocharov och Yuri Gurevich, "Optimala ancillafria Pauli+V-kretsar för axiella rotationer" Journal of Mathematical Physics 56, 122201 (2015).
https: / / doi.org/ 10.1063 / 1.4936990
arXiv: 1412.1033

[5] Michael Beverland, Earl Campbell, Mark Howard och Vadym Kliuchnikov, "Lägre gränser för icke-Clifford-resurserna för kvantberäkningar" Quantum Science and Technology 5, 035009 (2020).
https: / / doi.org/ 10.1088 / 2058-9565 / ab8963
arXiv: 1904.01124

[6] Michael E. Beverland, Prakash Murali, Matthias Troyer, Krysta M. Svore, Torsten Hoefler, Vadym Kliuchnikov, Guang Hao Low, Mathias Soeken, Aarthi Sundaram och Alexander Vaschillo, “Assessing requirements to scale to practice quantum advantage” (2022).
https://​/​doi.org/​10.48550/​arXiv.2211.07629
arXiv: 2211.07629

[7] Jean Bourgainand Alex Gamburd "A Spectral Gap Theorem in SU$(d)$" Journal of the European Mathematical Society 14, 1455–1511 (2012).
https://​/​doi.org/​10.4171/​JEMS/​337

[8] Alex Bocharov, Yuri Gurevich och Krysta M. Svore, "Effektiv sönderdelning av Single-Qubit Gates into V Basis Circuits" Fysisk översyn A 88, 1–13 (2013).
https: / / doi.org/ 10.1103 / PhysRevA.88.012313
arXiv: 1303.1411

[9] Sergey Bravyian och Alexei Kitaev "Universell kvantberäkning med idealiska Clifford-portar och bullriga ancillas" Phys. Rev. A 71, 022316 (2005).
https: / / doi.org/ 10.1103 / PhysRevA.71.022316

[10] Sergey Bravyian och Robert König "Klassificering av topologiskt skyddade portar för lokala stabilisatorkoder" Phys. Rev. Lett. 110, 170503 (2013).
https: / / doi.org/ 10.1103 / PhysRevLett.110.170503

[11] Michael E. Beverland, Aleksander Kubica och Krysta M. Svore, "Cost of Universality: A Comparative Study of the Overhead of State Destillation and Code Switching with Color Codes" PRX Quantum 2, 020341 (2021).
https: / / doi.org/ 10.1103 / PRXQuantum.2.020341

[12] Alex Bocharov, Martin Roetteler och Krysta M Svore, "Efficient Synthesis of Universal Repeat-Until-Success Quantum Circuits" Physical Review Letters 114, 080502 (2015).
https: / / doi.org/ 10.1103 / PhysRevLett.114.080502
arXiv: 1404.5320

[13] Alex Bocharov, Martin Roetteler och Krysta M. Svore, "Effektiv syntes av probabilistiska kvantkretsar med reserv" Physical Review A 91, 052317 (2015).
https: / / doi.org/ 10.1103 / PhysRevA.91.052317
arXiv: 1409.3552

[14] Vera von Burg, Guang Hao Low, Thomas Häner, Damian S. Steiger, Markus Reiher, Martin Roetteler och Matthias Troyer, "Quantum computing enhanced computational catalysis" Phys. Rev. Research 3, 033055 (2021).
https: / / doi.org/ 10.1103 / PhysRevResearch.3.033055

[15] Earl Campbell "Kortare grindsekvenser för kvantberäkning genom att blanda enhetliga enheter" Physical Review A 95 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.95.042306
arXiv: 1612.02689

[16] Andrew M. Childs, Yuan Su, Minh C. Tran, Nathan Wiebe och Shuchen Zhu, "Theory of Trotter Error with Commutator Scaling" Phys. Rev. X 11, 011020 (2021).
https: / / doi.org/ 10.1103 / PhysRevX.11.011020

[17] Denis X. Charles, Kristin E. Lauter och Eyal Z. Goren, "Cryptographic Hash Functions from Expander Graphs" Journal of Cryptology 22, 93–113 (2009).
https: / / doi.org/ 10.1007 / s00145-007-9002-x

[18] Henri Cohen "Advanced Topics in Computional Number Theory" Springer New York (2000).
https:/​/​doi.org/​10.1007/​978-1-4419-8489-0

[19] Henri Cohen "A Course in Computational Algebraic Number Theory" Springer Berlin Heidelberg (1993).
https:/​/​doi.org/​10.1007/​978-3-662-02945-9

[20] Shorter Quantum Circuits Dataset (2023).
https://​/​azure-quantum-notebooks.azurefd.net/​publicdata/​shorter-quantum-circuits-dataset.tar

[21] Bryan Eastinand Emanuel Knill "Restrictions on Transversal Encoded Quantum Gate Sets" Phys. Rev. Lett. 102, 110502 (2009).
https: / / doi.org/ 10.1103 / PhysRevLett.102.110502

[22] Simon Forest, David Gosset, Vadym Kliuchnikov och David McKinnon, "Exakt syntes av enstaka qubit-enheter över Clifford-cyklotomiska grinduppsättningar" Journal of Mathematical Physics 56, 082201 (2015).
https: / / doi.org/ 10.1063 / 1.4927100

[23] Daniel Gottesman och Isaac L. Chuang "Demonstrera viabiliteten av universell kvantberäkning med hjälp av teleportering och en-qubit-operationer" Nature 402, 390–393 (1999).
https: / / doi.org/ 10.1038 / 46503

[24] Craig Gidney och Austin G. Fowler "Effektiva magiska tillståndsfabriker med en katalyserad $|CCZ⟩$ till $2|T⟩$ transformation" Quantum 3, 135 (2019).
https:/​/​doi.org/​10.22331/​q-2019-04-30-135

[25] Joachim von zur Gathen och Jürgen Gerhard "Modern Computer Algebra" Cambridge University Press (2013).
https: / / doi.org/ 10.1017 / CBO9781139856065

[26] Craig Gidney "Halving the cost of quantum addition" Quantum 2, 74 (2018).
https:/​/​doi.org/​10.22331/​q-2018-06-18-74

[27] David Gosset, Vadym Kliuchnikov, Michele Mosca och Vincent Russo, "An Algorithm for the T-Count" Quantum Info. Comput. 14, 1261–1276 (2014).
https://​/​doi.org/​10.48550/​arXiv.1308.4134

[28] Matthew B. Hastings "Turning gate synthesis errors into incoherent errors" Quantum Information and Computation 17, 488–494 (2017).
https://​/​doi.org/​10.48550/​arXiv.1612.01011
arXiv: 1612.01011

[29] Aram W. Harrow, Benjamin Recht och Isaac L. Chuang, ”Effektiva diskreta approximationer av kvantportar” Journal of Mathematical Physics 43, 4445–4451 (2002).
https: / / doi.org/ 10.1063 / 1.1495899

[30] Kenneth Ireland och Michael Rosen "A Classical Introduction to Modern Number Theory" Springer New York (1990).
https:/​/​doi.org/​10.1007/​978-1-4757-2103-4

[31] Raban Iten, Roger Colbeck, Ivan Kukuljan, Jonathan Home och Matthias Christandl, "Quantum circuits for isometries" Phys. Rev. A 93, 032318 (2016).
https: / / doi.org/ 10.1103 / PhysRevA.93.032318

[32] Raban Iten, Oliver Reardon-Smith, Emanuel Malvetti, Luca Mondada, Gabrielle Pauvert, Ethan Redmond, Ravjot Singh Kohli och Roger Colbeck, "Introduction to UniversalQCompiler" (2021).
https://​/​doi.org/​10.48550/​arXiv.1904.01072
arXiv: 1904.01072

[33] Nathaniel Johnston, David W. Kribs och Vern I. Paulsen, "Computing Stabilized Norms for Quantum Operations via theory of Completely Bounded Maps" Quantum Info. Comput. 9, 16–35 (2009).
https://​/​doi.org/​10.48550/​arXiv.0711.3636

[34] Aleksandr Yakovlevich Khinchin "En kvantitativ formulering av Kroneckers approximationsteorin" Izvestiya Rossiiskoi Akademii Nauk. Seriya Matemacheskaya 12, 113–122 (1948).

[35] V Kliuchnikov, A Bocharov, M Roetteler och J Yard, "A Framework for Approximating Qubit Unitaries" (2015).
https://​/​doi.org/​10.48550/​arXiv.1510.03888
arXiv: 1510.03888

[36] Phillip Kaye, Raymond Laflamme och Michele Mosca, "An Introduction to Quantum Computing" Oxford University Press (2006).
https: / / doi.org/ 10.1093 / oso / 9780198570004.001.0001

[37] V Kliuchnikov, D Maslov och M Mosca, "Asymptotiskt Optimal Approximation of Single Qubit Unitities by Clifford and T Circuits Using a Constant Number of Acillary Qubits" Physical Review Letters 110, 190502 (2013).
https: / / doi.org/ 10.1103 / PhysRevLett.110.190502
arXiv: 1212.0822

[38] Vadym Kliuchnikov, Dmitri Maslov och Michele Mosca, "Snabb och effektiv exakt syntes av enkel-Qubit-enheter genererade av Clifford och T Gates" Quantum Info. Comput. 13, 607–630 (2013).
https://​/​doi.org/​10.48550/​arXiv.1206.5236

[39] V Kliuchnikovand J Yard "Ett ramverk för exakt syntes" (2015).
https://​/​doi.org/​10.48550/​arXiv.1504.04350
arXiv: 1504.04350

[40] Guang Hao Lowand Isaac L. Chuang "Optimal Hamiltonian Simulation by Quantum Signal Processing" Phys. Rev. Lett. 118, 010501 (2017).
https: / / doi.org/ 10.1103 / PhysRevLett.118.010501

[41] Franz Lemmermeyer ”Den euklidiska algoritmen i algebraiska talfält” Expositiones Mathematicae 13, 385–416 (1995).

[42] HW Lenstra ”Heltalsprogrammering med ett fast antal variabler” Mathematics of Operations Research 8, 538–548 (1983).
https: / ⠀ </ ⠀ <doi.org/†<10.1287 / ⠀ <moor.8.4.538

[43] Daniel Litinski "A Game of Surface Codes: Large-Scale Quantum Computing with Lattice Surgery" Quantum 3, 128 (2019).
https:/​/​doi.org/​10.22331/​q-2019-03-05-128

[44] AK Lenstra, HW Lenstra och L. Lovász, "Faktorering av polynom med rationella koefficienter" Mathematische Annalen 261, 515–534 (1982).
https: / / doi.org/ 10.1007 / BF01457454

[45] A. Lubotzky, R. Phillips och P. Sarnak, "Ramanujan graphs" Combinatorica 8, 261–277 (1988).
https: / / doi.org/ 10.1007 / BF02126799

[46] Easwar Magesan, Jay M. Gambetta och Joseph Emerson, "Karakterisering av kvantgrindar via randomiserad benchmarking" Phys. Rev A 85, 042311 (2012).
https: / / doi.org/ 10.1103 / PhysRevA.85.042311

[47] Emanuel Malvetti, Raban Iten och Roger Colbeck, "Quantum Circuits for Sparse Isometries" Quantum 5, 412 (2021).
https:/​/​doi.org/​10.22331/​q-2021-03-15-412

[48] Michael A. Nielsen och Isaac L. Chuang ”Quantum Computation and Quantum Information” Cambridge University Press (2012).
https: / / doi.org/ 10.1017 / CBO9780511976667

[49] Shorter Quantum Circuits Notebook (2023).
https:/​/​github.com/​microsoft/​Quantum/​blob/​a57178163b64a060d37603355c8a78571075f679/​samples/​azure-quantum/​shorter-quantum-circuits/​shorter-quantum-circuits-dataset.ipynb

[50] Gabriele Nebe, Eric M. Rains och Neil JA Sloane, "Real and Complex Clifford Groups" Springer Berlin Heidelberg (2006).
https:/​/​doi.org/​10.1007/​3-540-30731-1_6

[51] Yunseong Nam, Yuan Su och Dmitri Maslov, "Ungefärlig kvantfouriertransform med O(n log(n)) T-grindar" npj Quantum Information 6, 26 (2020).
https:/​/​doi.org/​10.1038/​s41534-020-0257-5

[52] Christophe Petit, Kristin Lauter och Jean-Jacques Quisquater, "Fullständig krypteringsanalys av LPS och Morgensterns hashfunktioner" (2008).
https:/​/​doi.org/​10.1007/​978-3-540-85855-3_18

[53] Eduardo Carvalho Pinto och Christophe Petit "Better path-finding algorithms in LPS Ramanujan graphs" Journal of Mathematical Cryptology 12, 191–202 (2018).
https: / / doi.org/ 10.1515 / jmc-2017-0051

[54] Adam Paetznick och Krysta M. Svore "Repeat-till-success: Non-deterministic decomposition of single-qubit unitaries" Quantum Information and Computation 14, 1277–1301 (2014).
https://​/​doi.org/​10.48550/​arXiv.1311.1074
arXiv: 1311.1074

[55] Ori Parzanchevski och Peter Sarnak "Super-Golden-Gates for PU(2)" Advances in Mathematics 327, 869–901 (2018) Specialvolym som hedrar David Kazhdan.
https: / / doi.org/ 10.1016 / j.aim.2017.06.022

[56] Neil J. Ross "Optimal Ancilla-Free Clifford+V Approximation of Z-Rotations" Quantum Info. Comput. 15, 932–950 (2015).
https://​/​doi.org/​10.48550/​arXiv.1409.4355

[57] Neil J. Rossand Peter Selinger "Optimal ancilla-fri Clifford+T approximation of z-rotations" Quantum Information & Computation 15, 932–950 (2015).
https://​/​doi.org/​10.48550/​arXiv.1403.2975
arXiv: 1403.2975

[58] Peter Sarnak "Brev till Aaronson och Pollington om Solvay-Kitaevs teorem och Golden Gates, 2015".
http: / / publications.ias.edu/ sarnak / paper / 2637

[59] Naser T Sardari "Complexity of Strong Approximation on the Sphere" International Mathematics Research Notices 2021, 13839–13866 (2021).
https://​/​doi.org/​10.1093/​imrn/​rnz233

[60] Peter Selinger "Efficient Clifford+T approximation of single-qubit operators" Quantum Information & Computation 15, 159–180 (2015).
https://​/​doi.org/​10.48550/​arXiv.1212.6253
arXiv: 1212.6253

[61] Zachary Stier privat kommunikation (2020).

[62] Jean-Pierre Tillich och Gilles Zémor "Kollisioner för LPS expander graph hash function" Årlig internationell konferens om teorin och tillämpningarna av kryptografiska tekniker 254–269 (2008).
https:/​/​doi.org/​10.1007/​978-3-540-78967-3_15

[63] John Voight "Quaternion Algebras" Springer International Publishing (2021).
https:/​/​doi.org/​10.1007/​978-3-030-56694-4

[64] Lawrence C. Washington "Introduktion till cyklotomiska fält" Springer New York (1997).
https:/​/​doi.org/​10.1007/​978-1-4612-1934-7

[65] John Watrous "The Theory of Quantum Information" Cambridge University Press (2018).
https: / / doi.org/ 10.1017 / 9781316848142

[66] Paul Webster och Stephen D. Bartlett "Feltoleranta kvantportar med defekter i topologiska stabilisatorkoder" Phys. Rev. A 102, 022403 (2020).
https: / / doi.org/ 10.1103 / PhysRevA.102.022403

Citerad av

[1] Daniel Litinski och Naomi Nickerson, "Aktiv volym: En arkitektur för effektiva feltoleranta kvantdatorer med begränsade icke-lokala anslutningar", arXiv: 2211.15465, (2022).

[2] Pascal Baßler, Matthias Zipper, Christopher Cedzich, Markus Heinrich, Patrick H. Huber, Michael Johanning och Martin Kliesch, "Synthesis of and compilation with time-optimal multi-qubit gates", Quantum 7, 984 (2023).

[3] Seiseki Akibue, Go Kato och Seiichiro Tani, "Probabilistisk enhetssyntes med optimal noggrannhet", arXiv: 2301.06307, (2023).

[4] Thomas Lubinski, Cassandra Granade, Amos Anderson, Alan Geller, Martin Roetteler, Andrei Petrenko och Bettina Heim, "Avancera hybrid kvantklassisk beräkning med realtidsexekvering", Frontiers in Physics 10, 940293 (2022).

[5] Seiseki Akibue, Go Kato och Seiichiro Tani, "Probabilistisk tillståndssyntes baserad på optimal konvex approximation", arXiv: 2303.10860, (2023).

Ovanstående citat är från SAO / NASA ADS (senast uppdaterad framgångsrikt 2023-12-19 01:59:59). 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 2023-12-19 01:59:58).

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.

Tidsstämpel:

Mer från Quantum Journal