Shorter Quantum Circuits Via Single-qubit Gate Approximation

Republished By Plato

Followers: 0

Vadym Kliuchnikov^1,2, Kristin Lauter³, Romy Minko^4,5, Adam Paetznick¹, and Christophe Petit^6,7

¹Microsoft Quantum, Redmond, WA, US
²Microsoft Quantum, Toronto, ON, CA
³Facebook AI Research, Seattle, WA, US
⁴University of Oxford, Oxford, UK
⁵Heilbronn Institute for Mathematical Research, University of Bristol, Bristol, UK
⁶University of Birmingham, Birmingham, UK
⁷Université Libre de Bruxelles, Brussels, Belgium

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

We give a novel procedure for approximating general single-qubit unitaries from a finite universal gate set by reducing the problem to a novel magnitude approximation problem, achieving an immediate improvement in sequence length by a factor of 7/9. Extending the works [28] and [15], we show that taking probabilistic mixtures of channels to solve fallback [13] and magnitude approximation problems saves factor of two in approximation costs. In particular, over the Clifford+$sqrt{mathrm{T}}$ gate set we achieve an average non-Clifford gate count of $0.23log_2(1/varepsilon)+2.13$ and T-count $0.56log_2(1/varepsilon)+5.3$ with mixed fallback approximations for diamond norm accuracy $varepsilon$.
This paper provides a holistic overview of gate approximation, in addition to these new insights. We give an end-to-end procedure for gate approximation for general gate sets related to some quaternion algebras, providing pedagogical examples using common fault-tolerant gate sets (V, Clifford+T and Clifford+$sqrt{mathrm{T}}$). We also provide detailed numerical results for Clifford+T and Clifford+$sqrt{mathrm{T}}$ gate sets. In an effort to keep the paper self-contained, we include an overview of the relevant algorithms for integer point enumeration and relative norm equation solving. We provide a number of further applications of the magnitude approximation problems, as well as improved algorithms for exact synthesis, in the Appendices.

► BibTeX data

@article{Kliuchnikov2023shorterquantum, doi = {10.22331/q-2023-12-18-1208}, url = {https://doi.org/10.22331/q-2023-12-18-1208}, title = {Shorter quantum circuits via single-qubit gate approximation}, author = {Kliuchnikov, Vadym and Lauter, Kristin and Minko, Romy and Paetznick, Adam and Petit, Christophe}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {7}, pages = {1208}, month = dec, year = {2023}<br /> }

► References

[1] Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C. Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando G. S. L. 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, and John M. Martinis, “Quantum supremacy using a programmable superconducting processor” Nature 574, 505-510 (2019).
https://doi.org/10.1038/s41586-019-1666-5

[2] Wojciech Banaszczyk “Inequalities for convex bodies and polar reciprocal lattices in $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, and Harald Weinfurter, “Elementary gates for quantum computation” Physical Review A 52, 3457–3467 (1995).
https://doi.org/10.1103/PhysRevA.52.3457

[4] Andreas Blass, Alex Bocharov, and Yuri Gurevich, “Optimal ancilla-free Pauli+V circuits for axial rotations” Journal of Mathematical Physics 56, 122201 (2015).
https://doi.org/10.1063/1.4936990
arXiv:1412.1033

[5] Michael Beverland, Earl Campbell, Mark Howard, and Vadym Kliuchnikov, “Lower bounds on the non-Clifford resources for quantum computations” 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, and Alexander Vaschillo, “Assessing requirements to scale to practical 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, and Krysta M. Svore, “Efficient Decomposition of Single-Qubit Gates into V Basis Circuits” Physical Review A 88, 1–13 (2013).
https://doi.org/10.1103/PhysRevA.88.012313
arXiv:1303.1411

[9] Sergey Bravyiand Alexei Kitaev “Universal quantum computation with ideal Clifford gates and noisy ancillas” Phys. Rev. A 71, 022316 (2005).
https://doi.org/10.1103/PhysRevA.71.022316

[10] Sergey Bravyiand Robert König “Classification of Topologically Protected Gates for Local Stabilizer Codes” Phys. Rev. Lett. 110, 170503 (2013).
https://doi.org/10.1103/PhysRevLett.110.170503

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

[12] Alex Bocharov, Martin Roetteler, and 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, and Krysta M. Svore, “Efficient synthesis of probabilistic quantum circuits with fallback” 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, and Matthias Troyer, “Quantum computing enhanced computational catalysis” Phys. Rev. Research 3, 033055 (2021).
https://doi.org/10.1103/PhysRevResearch.3.033055

[15] Earl Campbell “Shorter gate sequences for quantum computing by mixing unitaries” 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, and 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, and 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, and David McKinnon, “Exact synthesis of single-qubit unitaries over Clifford-cyclotomic gate sets” Journal of Mathematical Physics 56, 082201 (2015).
https://doi.org/10.1063/1.4927100

[23] Daniel Gottesmanand Isaac L. Chuang “Demonstrating the viability of universal quantum computation using teleportation and single-qubit operations” Nature 402, 390–393 (1999).
https://doi.org/10.1038/46503

[24] Craig Gidneyand Austin G. Fowler “Efficient magic state factories with a catalyzed $|CCZ⟩$ to $2|T⟩$ transformation” Quantum 3, 135 (2019).
https://doi.org/10.22331/q-2019-04-30-135

[25] Joachim von zur Gathenand 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, and 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, and Isaac L. Chuang, “Efficient discrete approximations of quantum gates” Journal of Mathematical Physics 43, 4445–4451 (2002).
https://doi.org/10.1063/1.1495899

[30] Kenneth Irelandand 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, and 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, and Roger Colbeck, “Introduction to UniversalQCompiler” (2021).
https://doi.org/10.48550/arXiv.1904.01072
arXiv:1904.01072

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

[34] Aleksandr Yakovlevich Khinchin “A quantitative formulation of the approximation theory of Kronecker” Izvestiya Rossiiskoi Akademii Nauk. Seriya Matematicheskaya 12, 113–122 (1948).

[35] V Kliuchnikov, A Bocharov, M Roetteler, and 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, and 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, and M Mosca, “Asymptotically Optimal Approximation of Single Qubit Unitaries by Clifford and T Circuits Using a Constant Number of Ancillary Qubits” Physical Review Letters 110, 190502 (2013).
https://doi.org/10.1103/PhysRevLett.110.190502
arXiv:1212.0822

[38] Vadym Kliuchnikov, Dmitri Maslov, and Michele Mosca, “Fast and Efficient Exact Synthesis of Single-Qubit Unitaries Generated by Clifford and T Gates” Quantum Info. Comput. 13, 607–630 (2013).
https://doi.org/10.48550/arXiv.1206.5236

[39] V Kliuchnikovand J Yard “A framework for exact synthesis” (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 “The Euclidean algorithm in algebraic number fields” Expositiones Mathematicae 13, 385–416 (1995).

[42] H. W. Lenstra “Integer Programming with a Fixed Number of Variables” 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] A. K. Lenstra, H. W. Lenstra, and L. Lovász, “Factoring polynomials with rational coefficients” Mathematische Annalen 261, 515–534 (1982).
https://doi.org/10.1007/BF01457454

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

[46] Easwar Magesan, Jay M. Gambetta, and Joseph Emerson, “Characterizing quantum gates via randomized benchmarking” Phys. Rev. A 85, 042311 (2012).
https://doi.org/10.1103/PhysRevA.85.042311

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

[48] Michael A. Nielsenand 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, and Neil J.A. 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, and Dmitri Maslov, “Approximate quantum Fourier transform with O(n log(n)) T gates” npj Quantum Information 6, 26 (2020).
https://doi.org/10.1038/s41534-020-0257-5

[52] Christophe Petit, Kristin Lauter, and Jean-Jacques Quisquater, “Full Cryptanalysis of LPS and Morgenstern Hash Functions” (2008).
https://doi.org/10.1007/978-3-540-85855-3_18

[53] Eduardo Carvalho Pintoand 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 Paetznickand Krysta M. Svore “Repeat-until-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 Parzanchevskiand Peter Sarnak “Super-Golden-Gates for PU(2)” Advances in Mathematics 327, 869–901 (2018) Special volume honoring 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-free 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 “Letter to Aaronson and Pollington on the Solvay-Kitaev Theorem and 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 private communication (2020).

[62] Jean-Pierre Tillichand Gilles Zémor “Collisions for the LPS expander graph hash function” Annual International Conference on the Theory and Applications of Cryptographic Techniques 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 “Introduction to Cyclotomic Fields” 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 Websterand Stephen D. Bartlett “Fault-tolerant quantum gates with defects in topological stabilizer codes” Phys. Rev. A 102, 022403 (2020).
https://doi.org/10.1103/PhysRevA.102.022403

Cited by

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

[2] Daniel Litinski and Naomi Nickerson, “Active volume: An architecture for efficient fault-tolerant quantum computers with limited non-local connections”, arXiv:2211.15465, (2022).

[3] Seiseki Akibue, Go Kato, and Seiichiro Tani, “Probabilistic unitary synthesis with optimal accuracy”, arXiv:2301.06307, (2023).

[4] Thomas Lubinski, Cassandra Granade, Amos Anderson, Alan Geller, Martin Roetteler, Andrei Petrenko, and Bettina Heim, “Advancing hybrid quantum-classical computation with real-time execution”, Frontiers in Physics 10, 940293 (2022).

[5] Seiseki Akibue, Go Kato, and Seiichiro Tani, “Probabilistic state synthesis based on optimal convex approximation”, arXiv:2303.10860, (2023).

The above citations are from SAO/NASA ADS (last updated successfully 2023-12-23 14:07:47). The list may be incomplete as not all publishers provide suitable and complete citation data.

On Crossref’s cited-by service no data on citing works was found (last attempt 2023-12-23 14:07:45).

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.

SEO Powered Content & PR Distribution. Get Amplified Today.
PlatoData.Network Vertical Generative Ai. Empower Yourself. Access Here.
PlatoAiStream. Web3 Intelligence. Knowledge Amplified. Access Here.
PlatoESG. Carbon, CleanTech, Energy, Environment, Solar, Waste Management. Access Here.
PlatoHealth. Biotech and Clinical Trials Intelligence. Access Here.
Source: https://quantum-journal.org/papers/q-2023-12-18-1208/

Time Stamp: December 18, 2023

Time Stamp: Jan 4, 2024

Republished By Plato

Abstract

► BibTeX data

► References

Cited by

Extending the fair sampling assumption using causal diagrams

Quantum circuits for solving local fermion-to-qubit mappings

Quantum Methods for Neural Networks and Application to Medical Image Classification

Efficient Verification of Ground States of Frustration-Free Hamiltonians

Signature of exceptional point phase transition in Hermitian systems

Does causal dynamics imply local interactions?

The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size

Quantum Deep Hedging

Thermal Area Law for Lattice Bosons

A probabilistic view of wave-particle duality for single photons

Quantum-optimal information encoding using noisy passive linear optics

About Us

Vertical Search & Ai

Platform

Stay Connected

Account