Halving the cost of quantum addition

Craig Gidney

Google, Santa Barbara, CA 93117, USA

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

Abstract

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] Alexandru Paler, Oumarou Oumarou, and Robert Basmadjian, "Parallelizing the queries in a bucket-brigade quantum random access memory", Physical Review A 102 3, 032608 (2020).

[2] Joonho Lee, Dominic W. Berry, Craig Gidney, William J. Huggins, Jarrod R. McClean, Nathan Wiebe, and Ryan Babbush, "Even More Efficient Quantum Computations of Chemistry Through Tensor Hypercontraction", PRX Quantum 2 3, 030305 (2021).

[3] Yuval R. Sanders, Dominic W. Berry, Pedro C.S. Costa, Louis W. Tessler, Nathan Wiebe, Craig Gidney, Hartmut Neven, and Ryan Babbush, "Compilation of Fault-Tolerant Quantum Heuristics for Combinatorial Optimization", PRX Quantum 1 2, 020312 (2020).

[4] He Li, Hongxiang Fan, and Jiawei Liang, 2021 12th International Green and Sustainable Computing Conference (IGSC) 1 (2021) ISBN:978-1-6654-7851-9.

[5] Miguel-Angel Sicilia, Salvador Sánchez-Alonso, Marçal Mora-Cantallops, and Elena García-Barriocanal, Communications in Computer and Information Science 1266, 292 (2020) ISBN:978-3-030-58792-5.

[6] Michele Mosca and Priyanka Mukhopadhyay, "A polynomial time and space heuristic algorithm for T-count", Quantum Science and Technology 7 1, 015003 (2022).

[7] 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).

[8] Hyeongrak Choi, Mihir Pant, Saikat Guha, and Dirk Englund, "Percolation-based architecture for cluster state creation using photon-mediated entanglement between atomic memories", npj Quantum Information 5 1, 104 (2019).

[9] Craig Gidney and Martin Ekerå, "How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits", arXiv:1905.09749, Quantum 5, 433 (2021).

[10] Shengbin Wang, Zhimin Wang, Guolong Cui, Shangshang Shi, Ruimin Shang, Lixin Fan, Wendong Li, Zhiqiang Wei, and Yongjian Gu, "Fast black-box quantum state preparation based on linear combination of unitaries", Quantum Information Processing 20 8, 270 (2021).

[11] Himanshu Thapliyal, Edgard Munoz-Coreas, and Vladislav Khalus, 2020 IEEE 38th International Conference on Computer Design (ICCD) 5 (2020) ISBN:978-1-7281-9710-4.

[12] Edgard Munoz-Coreas and Himanshu Thapliyal, 2019 IEEE Computer Society Annual Symposium on VLSI (ISVLSI) 360 (2019) ISBN:978-1-7281-3391-1.

[13] Himanshu Thapliyal, Edgard Muñoz-Coreas, and Vladislav Khalus, "Quantum circuit designs of carry lookahead adder optimized for T-count T-depth and qubits", Sustainable Computing: Informatics and Systems 29, 100457 (2021).

[14] Bettina Heim, Mathias Soeken, Sarah Marshall, Chris Granade, Martin Roetteler, Alan Geller, Matthias Troyer, and Krysta Svore, "Quantum programming languages", Nature Reviews Physics 2 12, 709 (2020).

[15] Giulia Meuli, Mathias Soeken, and Giovanni De Micheli, "Xor-And-Inverter Graphs for Quantum Compilation", npj Quantum Information 8 1, 7 (2022).

[16] Giulia Meuli, Mathias Soeken, Martin Roetteler, and Giovanni De Micheli, 2020 IEEE International Symposium on Circuits and Systems (ISCAS) 1 (2020) ISBN:978-1-7281-3320-1.

[17] Yunseong Nam, Yuan Su, and Dmitri Maslov, "Approximate quantum Fourier transform with O(n log(n)) T gates", arXiv:1803.04933, npj Quantum Information 6 1, 26 (2020).

[18] Matthew Amy and Neil J. Ross, "Phase-state duality in reversible circuit design", Physical Review A 104 5, 052602 (2021).

[19] Michael Beverland, Earl Campbell, Mark Howard, and Vadym Kliuchnikov, "Lower bounds on the non-Clifford resources for quantum computations", Quantum Science and Technology 5 3, 035009 (2020).

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

[21] Annie Y. Wei, Preksha Naik, Aram W. Harrow, and Jesse Thaler, "Quantum algorithms for jet clustering", Physical Review D 101 9, 094015 (2020).

[22] Élie Gouzien and Nicolas Sangouard, "Factoring 2048-bit RSA Integers in 177 Days with 13 436 Qubits and a Multimode Memory", Physical Review Letters 127 14, 140503 (2021).

[23] Thomas Häner and Mathias Soeken, "Lowering the T-depth of Quantum Circuits via Logic Network Optimization", ACM Transactions on Quantum Computing 3 2, 1 (2022).

[24] Gary J. Mooney, Charles D. Hill, and Lloyd C. L. Hollenberg, "Cost-optimal single-qubit gate synthesis in the Clifford hierarchy", Quantum 5, 396 (2021).

[25] Austin Gilliam, Stefan Woerner, and Constantin Gonciulea, "Grover Adaptive Search for Constrained Polynomial Binary Optimization", Quantum 5, 428 (2021).

[26] Daniel Litinski, "Magic State Distillation: Not as Costly as You Think", Quantum 3, 205 (2019).

[27] Alexandru Paler and Robert Basmadjian, 2019 IEEE/ACM International Symposium on Nanoscale Architectures (NANOARCH) 1 (2019) ISBN:978-1-7281-5520-3.

[28] F. Orts, G. Ortega, A. C. Cucura, E. Filatovas, and E. M. Garzón, "Optimal fault-tolerant quantum comparators for image binarization", The Journal of Supercomputing 77 8, 8433 (2021).

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

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

[31] Sohrab Sajadimanesh, Jean Paul Latyr Faye, and Ehsan Atoofian, Proceedings of the 19th ACM International Conference on Computing Frontiers 121 (2022) ISBN:9781450393386.

[32] Francisco Orts, Gloria Ortega, Ernestas Filatovas, and Ester M. Garzón, "Implementation of three efficient 4-digit fault-tolerant quantum carry lookahead adders", The Journal of Supercomputing (2022).

[33] Edgard Munoz-Coreas and Himanshu Thapliyal, 2018 Ninth International Green and Sustainable Computing Conference (IGSC) 1 (2018) ISBN:978-1-5386-7466-6.

[34] Alexandru Paler, Oumarou Oumarou, and Robert Basmadjian, "On the Realistic Worst-Case Analysis of Quantum Arithmetic Circuits", IEEE Transactions on Quantum Engineering 3, 1 (2022).

[35] Alexander F. Shaw, Pavel Lougovski, Jesse R. Stryker, and Nathan Wiebe, "Quantum Algorithms for Simulating the Lattice Schwinger Model", Quantum 4, 306 (2020).

[36] Bruno Schmitt, Fereshte Mozafari, Giulia Meuli, Heinz Riener, and Giovanni De Micheli, 2021 Design, Automation & Test in Europe Conference & Exhibition (DATE) 1044 (2021) ISBN:978-3-9819263-5-4.

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

[38] Harashta Tatimma Larasati and Howon Kim, Lecture Notes in Computer Science 13009, 91 (2021) ISBN:978-3-030-89431-3.

[39] Ian D. Kivlichan, Craig Gidney, Dominic W. Berry, Nathan Wiebe, Jarrod McClean, Wei Sun, Zhang Jiang, Nicholas Rubin, Austin Fowler, Alán Aspuru-Guzik, Hartmut Neven, and Ryan Babbush, "Improved Fault-Tolerant Quantum Simulation of Condensed-Phase Correlated Electrons via Trotterization", Quantum 4, 296 (2020).

[40] Dominic W. Berry, Craig Gidney, Mario Motta, Jarrod R. McClean, and Ryan Babbush, "Qubitization of Arbitrary Basis Quantum Chemistry Leveraging Sparsity and Low Rank Factorization", Quantum 3, 208 (2019).

[41] Shengbin Wang, Zhimin Wang, Wendong Li, Lixin Fan, Guolong Cui, Zhiqiang Wei, and Yongjian Gu, "Quantum circuits design for evaluating transcendental functions based on a function-value binary expansion method", Quantum Information Processing 19 10, 347 (2020).

[42] Mathias Soeken, Mariia Mykhailova, Vadym Kliuchnikov, Christopher Granade, and Alexander Vaschillo, 2021 Design, Automation & Test in Europe Conference & Exhibition (DATE) 1050 (2021) ISBN:978-3-9819263-5-4.

[43] N M Guseynov and W V Pogosov, "Quantum simulation of fermionic systems using hybrid digital–analog quantum computing approach", Journal of Physics: Condensed Matter 34 28, 285901 (2022).

[44] Reza Azarderakhsh, Jean-François Biasse, Rami El Khatib, Brandon Langenberg, and Benjamin Pring, "Parallelism strategies for the tuneable golden-claw finding problem", International Journal of Computer Mathematics: Computer Systems Theory 6 4, 337 (2021).

[45] Kento Oonishi, Tomoki Tanaka, Shumpei Uno, Takahiko Satoh, Rodney Van Meter, and Noboru Kunihiro, "Efficient Construction of a Control Modular Adder on a Carry-Lookahead Adder Using Relative-Phase Toffoli Gates", IEEE Transactions on Quantum Engineering 3, 1 (2022).

[46] Thomas Häner, Samuel Jaques, Michael Naehrig, Martin Roetteler, and Mathias Soeken, Lecture Notes in Computer Science 12100, 425 (2020) ISBN:978-3-030-44222-4.

[47] Johannes Bausch, Sathyawageeswar Subramanian, and Stephen Piddock, "A quantum search decoder for natural language processing", Quantum Machine Intelligence 3 1, 16 (2021).

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

[49] Qingfeng Wang, Ming Li, Christopher Monroe, and Yunseong Nam, "Resource-Optimized Fermionic Local-Hamiltonian Simulation on a Quantum Computer for Quantum Chemistry", Quantum 5, 509 (2021).

[50] 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).

[51] Earl T Campbell, "Early fault-tolerant simulations of the Hubbard model", Quantum Science and Technology 7 1, 015007 (2022).

[52] Bruno Schmitt, Ali Javadi-Abhari, and Giovanni De Micheli, 2021 Design, Automation & Test in Europe Conference & Exhibition (DATE) 964 (2021) ISBN:978-3-9819263-5-4.

[53] Christopher Chamberland, Kyungjoo Noh, Patricio Arrangoiz-Arriola, Earl T. Campbell, Connor T. Hann, Joseph Iverson, Harald Putterman, Thomas C. Bohdanowicz, Steven T. Flammia, Andrew Keller, Gil Refael, John Preskill, Liang Jiang, Amir H. Safavi-Naeini, Oskar Painter, and Fernando G.S.L. Brandão, "Building a Fault-Tolerant Quantum Computer Using Concatenated Cat Codes", PRX Quantum 3 1, 010329 (2022).

[54] S. S. Gayathri, R. Kumar, Samiappan Dhanalakshmi, and Brajesh Kumar Kaushik, "T-count optimized quantum circuit for floating point addition and multiplication", Quantum Information Processing 20 11, 378 (2021).

[55] Christopher Chamberland and Earl T. Campbell, "Universal Quantum Computing with Twist-Free and Temporally Encoded Lattice Surgery", PRX Quantum 3 1, 010331 (2022).

[56] 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).

[57] Mathias Soeken and Martin Roetteler, 2020 IEEE International Conference on Quantum Computing and Engineering (QCE) 366 (2020) ISBN:978-1-7281-8969-7.

[58] S. S. Gayathri, R. Kumar, Samiappan Dhanalakshmi, Gerard Dooly, and Dinesh Babu Duraibabu, "T-Count Optimized Quantum Circuit Designs for Single-Precision Floating-Point Division", Electronics 10 6, 703 (2021).

[59] Yudong Cao, Jonathan Romero, Jonathan P. Olson, Matthias Degroote, Peter D. Johnson, Mária Kieferová, Ian D. Kivlichan, Tim Menke, Borja Peropadre, Nicolas P. D. Sawaya, Sukin Sim, Libor Veis, and Alán Aspuru-Guzik, "Quantum Chemistry in the Age of Quantum Computing", Chemical Reviews 119 19, 10856 (2019).

[60] Andreas Fischer and Alexandru Paler, Proceedings of the 34th ACM/SIGAPP Symposium on Applied Computing 1378 (2019) ISBN:9781450359337.

[61] Yuan Su, Dominic W. Berry, Nathan Wiebe, Nicholas Rubin, and Ryan Babbush, "Fault-Tolerant Quantum Simulations of Chemistry in First Quantization", PRX Quantum 2 4, 040332 (2021).

[62] Sam McArdle, "Learning from Physics Experiments with Quantum Computers: Applications in Muon Spectroscopy", PRX Quantum 2 2, 020349 (2021).

[63] 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).

[64] Hai-Sheng Li, Ping Fan, Haiying Xia, Huiling Peng, and Gui-Lu Long, "Efficient quantum arithmetic operation circuits for quantum image processing", Science China Physics, Mechanics, and Astronomy 63 8, 280311 (2020).

[65] Hai-Sheng Li, Ping Fan, Haiying Xia, and Gui-Lu Long, "The circuit design and optimization of quantum multiplier and divider", Science China Physics, Mechanics, and Astronomy 65 6, 260311 (2022).

[66] Niel de Beaudrap, Xiaoning Bian, and Quanlong Wang, "Fast and effective techniques for T-count reduction via spider nest identities", arXiv:2004.05164.

[67] Niel de Beaudrap, Xiaoning Bian, and Quanlong Wang, "Techniques to Reduce $\pi/4$-Parity-Phase Circuits, Motivated by the ZX Calculus", arXiv:1911.09039.

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

The above citations are from Crossref's cited-by service (last updated successfully 2022-05-18 06:28:50) and SAO/NASA ADS (last updated successfully 2022-05-18 06:28:51). The list may be incomplete as not all publishers provide suitable and complete citation data.