Halving the cost of quantum addition

Craig Gidney

Google, Santa Barbara, CA 93117, USA

We improve the number of T gates needed to perform an n-bit adder from $8n + O(1)$ to $4n + O(1)$. We do so via a "temporary logical-AND" construction which uses four T gates to store the logical-AND of two qubits into an ancilla and zero T gates to later erase the ancilla. This construction is equivalent to one by Jones, except that our framing makes it clear that the technique is far more widely applicable than previously realized. Temporary logical-ANDs can be applied to integer arithmetic, modular arithmetic, rotation synthesis, the quantum Fourier transform, Shor's algorithm, Grover oracles, and many other circuits. Because T gates dominate the cost of quantum computation based on the surface code, and temporary logical-ANDs are widely applicable, this represents a significant reduction in projected costs of quantum computation. In addition to our n-bit adder, we present an n-bit controlled adder circuit with T-count of $8n + O(1)$, a temporary adder that can be computed for the same cost as the normal adder but whose result can be kept until it is later uncomputed without using T gates, and discuss some other constructions whose T-count is improved by the temporary logical-AND.

► BibTeX data

► References

[1] M. Amy, D. Maslov, M. Mosca, and M. Roetteler. A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 32 (6): 818-830, jun 2013. 10.1109/​tcad.2013.2244643.
https:/​/​doi.org/​10.1109/​tcad.2013.2244643

[2] Ryan Babbush, Craig Gidney, Dominic W Berry, Nathan Wiebe, Jarrod McClean, Alexandru Paler, Austin Fowler, and Hartmut Neven. Encoding electronic spectra in quantum circuits with linear T complexity. arXiv preprint arXiv:1805.03662, 2018. URL https:/​/​arxiv.org/​abs/​1805.03662.
arXiv:1805.03662

[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 (5): 3457-3467, nov 1995. 10.1103/​physreva.52.3457.
https:/​/​doi.org/​10.1103/​physreva.52.3457

[4] R. Barends, J. Kelly, A. Megrant, A. Veitia, D. Sank, E. Jeffrey, T. C. White, J. Mutus, A. G. Fowler, B. Campbell, Y. Chen, Z. Chen, B. Chiaro, A. Dunsworth, C. Neill, P. O'Malley, P. Roushan, A. Vainsencher, J. Wenner, A. N. Korotkov, A. N. Cleland, and John M. Martinis. Superconducting quantum circuits at the surface code threshold for fault tolerance. Nature, 508: 500-503, 2014. 10.1038/​nature13171. arXiv:1402.4848.
https:/​/​doi.org/​10.1038/​nature13171
arXiv:1402.4848

[5] S. B. Bravyi and A. Yu. Kitaev. Quantum codes on a lattice with boundary. arXiv:quant-ph/​9811052, 1998. URL https:/​/​arxiv.org/​abs/​quant-ph/​9811052.
arXiv:quant-ph/9811052

[6] Richard P Brent and H-T_ Kung. A regular layout for parallel adders. IEEE transactions on Computers, (3): 260-264, 1982. 10.1109/​TC.1982.1675982.
https:/​/​doi.org/​10.1109/​TC.1982.1675982

[7] Steven A. Cuccaro, Thomas G. Draper, Samuel A. Kutin, and David Petrie Moulton. A new quantum ripple-carry addition circuit, 2004. URL https:/​/​arxiv.org/​abs/​quant-ph/​0410184.
arXiv:quant-ph/0410184

[8] E. Dennis, A. Kitaev, A. Landahl, and J. Preskill. Topological quantum memory. J. Math. Phys., 43: 4452-4505, 2002. 10.1063/​1.1499754. arXiv:quant-ph/​0110143.
https:/​/​doi.org/​10.1063/​1.1499754
arXiv:quant-ph/0110143

[9] Thomas G. Draper, Samuel A. Kutin, Eric M. Rains, and Krysta M. Svore. A logarithmic-depth quantum carry-lookahead adder. 2004. URL https:/​/​arxiv.org/​abs/​quant-ph/​0406142.
arXiv:quant-ph/0406142

[10] Austin Fowler, Dmitri Maslov, Cody Jones, and Matt Amy. Private correspondence, Aug 2017.

[11] Austin G. Fowler, Matteo Mariantoni, John M. Martinis, and Andrew N. Cleland. Surface codes: Towards practical large-scale quantum computation. Physical Review A, 86 (3), sep 2012. 10.1103/​physreva.86.032324.
https:/​/​doi.org/​10.1103/​physreva.86.032324

[12] J. M. Gambetta, J. M. Chow, and M. Steffen. Building logical qubits in a superconducting quantum computing system. npj Quantum Information, 3 (2), 2017. 10.1038/​s41534-016-0004-0. arXiv:1510.04375.
https:/​/​doi.org/​10.1038/​s41534-016-0004-0
arXiv:1510.04375

[13] Clare Horsman, Austin G Fowler, Simon Devitt, and Rodney Van Meter. Surface code quantum computing by lattice surgery. New Journal of Physics, 14 (12): 123011, 2012. 10.1088/​1367-2630/​14/​12/​123011.
https:/​/​doi.org/​10.1088/​1367-2630/​14/​12/​123011

[14] Mark Howard and Earl Campbell. Application of a resource theory for magic states to fault-tolerant quantum computing. Physical review letters, 118 (9): 090501, 2017. 10.1103/​PhysRevLett.118.090501.
https:/​/​doi.org/​10.1103/​PhysRevLett.118.090501

[15] Cody Jones. Low-overhead constructions for the fault-tolerant toffoli gate. Physical Review A, 87 (2), feb 2013. 10.1103/​physreva.87.022328.
https:/​/​doi.org/​10.1103/​physreva.87.022328

[16] Alexei Yu Kitaev, Alexander Shen, and Mikhail N Vyalyi. Classical and quantum computation. Number 47. American Mathematical Soc., 2002. 10.1090/​gsm/​047.
https:/​/​doi.org/​10.1090/​gsm/​047

[17] V. Lahtinen and J. K. Pachos. A short introduction to topological quantum computation. 10.21468/​SciPostPhys.3.3.021. URL https:/​/​arxiv.org/​abs/​1705.04103.
https:/​/​doi.org/​10.21468/​SciPostPhys.3.3.021
arXiv:1705.04103

[18] B. Lekitsch, S. Weidt, A. G. Fowler, K. Mølmer, S. J. Devitt, C. Wunderlich, and W. K. Hensinger. Blueprint for a microwave trapped-ion quantum computer. Science Advances, 3 (2): e1601540, 2017. 10.1126/​sciadv.1601540. arXiv:1508.00420.
https:/​/​doi.org/​10.1126/​sciadv.1601540
arXiv:1508.00420

[19] Edgard Muñoz-Coreas and Himanshu Thapliyal. T-count optimized design of quantum integer multiplication, 2017. URL https:/​/​arxiv.org/​abs/​1706.05113.
arXiv:1706.05113

[20] Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 2009. 10.1017/​cbo9780511976667.
https:/​/​doi.org/​10.1017/​cbo9780511976667

[21] R. Raussendorf and J. Harrington. Fault-tolerant quantum computation with high threshold in two dimensions. Phys. Rev. Lett., 98: 190504, 2007. 10.1103/​PhysRevLett.98.190504. arXiv:quant-ph/​0610082.
https:/​/​doi.org/​10.1103/​PhysRevLett.98.190504
arXiv:quant-ph/0610082

[22] Robert Raussendorf, Jim Harrington, and Kovid Goyal. Topological fault-tolerance in cluster state quantum computation. New Journal of Physics, 9 (6): 199, 2007. 10.1088/​1367-2630/​9/​6/​199.
https:/​/​doi.org/​10.1088/​1367-2630/​9/​6/​199

[23] Malte Schlosser, Sascha Tichelmann, Jens Kruse, and Gerhard Birkl. Scalable architecture for quantum information processing with atoms in optical micro-structures. Quantum Information Processing, 10 (6): 907, 2011. 10.1007/​s11128-011-0297-z. 1108.5136.
https:/​/​doi.org/​10.1007/​s11128-011-0297-z

Cited by

[1] Jesse R. Stryker, "Oracles for Gauss's law on digital quantum computers", Physical Review A 99 4, 042301 (2019).

[2] Craig Gidney and Austin G. Fowler, "Efficient magic state factories with a catalyzed |CCZ⟩ to 2|T⟩ transformation", Quantum 3, 135 (2019).

[3] Daniel Litinski, "A Game of Surface Codes: Large-Scale Quantum Computing with Lattice Surgery", Quantum 3, 128 (2019).

[4] Earl Campbell, Ankur Khurana, and Ashley Montanaro, "Applying quantum algorithms to constraint satisfaction problems", arXiv:1810.05582, Quantum 3, 167 (2019).

[5] Earl Campbell, "Random Compiler for Fast Hamiltonian Simulation", arXiv:1811.08017, Physical Review Letters 123 7, 070503 (2019).

[6] Yuval R. Sanders, Guang Hao Low, Artur Scherer, and Dominic W. Berry, "Black-Box Quantum State Preparation without Arithmetic", Physical Review Letters 122 2, 020502 (2019).

[7] Yunseong Nam and Dmitri Maslov, "Low-cost quantum circuits for classically intractable instances of the Hamiltonian dynamics simulation problem", npj Quantum Information 5 1, 44 (2019).

[8] Ryan Babbush, Dominic W. Berry, and Hartmut Neven, "Quantum simulation of the Sachdev-Ye-Kitaev model by asymmetric qubitization", Physical Review A 99 4, 040301 (2019).

[9] Alexandru Paler, "Controlling distilleries in fault-tolerant quantum circuits: problem statement and analysis towards a solution", arXiv:1806.07266.

[10] Yunseong Nam, Yuan Su, and Dmitri Maslov, "Approximate Quantum Fourier Transform with $O(n \log(n))$ T gates", arXiv:1803.04933.

[11] Ryan Babbush, Craig Gidney, Dominic W. Berry, Nathan Wiebe, Jarrod McClean, Alexandru Paler, Austin Fowler, and Hartmut Neven, "Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity", Physical Review X 8 4, 041015 (2018).

[12] Michael Beverland, Earl Campbell, Mark Howard, and Vadym Kliuchnikov, "Lower bounds on the non-Clifford resources for quantum computations", arXiv:1904.01124.

The above citations are from Crossref's cited-by service (last updated 2019-08-18 11:34:39) and SAO/NASA ADS (last updated 2019-08-18 11:34:40). The list may be incomplete as not all publishers provide suitable and complete citation data.