CoChat
Sign Up
PreprintCited by 9Quantum Computing Algorithms and ArchitectureQuantum Information and CryptographyQuantum many-body systems

The DOI matches its DataCite record.

Quantum-classical tradeoffs and multi-controlled quantum gate decompositions in variational algorithms

Open access
Tomesh, Teague, Allen, Nicholas, Dilley, Daniel, Saleem, Zain·2022·arXiv
DOI 10.48550/arxiv.2210.04378arXiv 2210.04378
Open this paper in CoChat — free accountOpen PDF

Abstract

The computational capabilities of near-term quantum computers are limited by the noisy execution of gate operations and a limited number of physical qubits. Hybrid variational algorithms are well-suited to near-term quantum devices because they allow for a wide range of tradeoffs between the amount of quantum and classical resources used to solve a problem. This paper investigates tradeoffs available at both the algorithmic and hardware levels by studying a specific case -- applying the Quantum Approximate Optimization Algorithm (QAOA) to instances of the Maximum Independent Set (MIS) problem. We consider three variants of the QAOA which offer different tradeoffs at the algorithmic level in terms of their required number of classical parameters, quantum gates, and iterations of classical optimization needed. Since MIS is a constrained combinatorial optimization problem, the QAOA must respect the problem constraints. This can be accomplished by using many multi-controlled gate operations which must be decomposed into gates executable by the target hardware. We study the tradeoffs available at this hardware level, combining the gate fidelities and decomposition efficiencies of different native gate sets into a single metric called the gate decomposition cost.

Overview

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

DataCite · 10.48550/arxiv.2210.04378

Cites

Statistics

Verification

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Citations

Cites

No references could be resolved yet.

Research works printed but not linked: 53

  1. Jay M Gambetta, Jerry M Chow, and Matthias Steffen. Building logical qubits in a super- conducting quantum computing system. npj Quantum Information, 3(1):1-7, 2017. https: //doi.org/10.1038/s41534-016-0004-0. · DOI
  2. K Wright, KM Beck, Sea Debnath, JM Amini, Y Nam, N Grzesiak, J-S Chen, NC Pisenti, M Chmielewski, C Collins, et al. Benchmark- ing an 11-qubit quantum computer. Nature communications, 10(1):1-6, 2019. https:// doi.org/10.1038/s41467-019-13534-2. · DOI
  3. Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C Bardin, Rami Barends, Ru- pak Biswas, Sergio Boixo, Fernando GSL Bran- dao, David A Buell, et al. Quantum supremacy using a programmable superconducting proces- sor. Nature, 574(7779):505-510, 2019. https: //doi.org/10.1038/s41586-019-1666-5. · DOI · Paper page
  4. JM Arrazola, V Bergholm, K Brádler, TR Brom- ley, MJ Collins, I Dhand, A Fumagalli, T Ger- rits, A Goussev, LG Helt, et al. Quan- tum circuits with many photons on a pro- grammable nanophotonic chip. Nature, 591 (7848):54-60, 2021. https://doi.org/10. 1038/s41586-021-03202-1. · DOI · Paper page
  5. Thomas Monz, Kihwan Kim, Wolfgang Hänsel, M Riebe, AS Villar, Philipp Schindler, Michael Chwalla, Markus Hennrich, and Rainer Blatt. Realization of the quantum toffoli gate with trapped ions. Physical review letters, 102 (4):040501, 2009. https://doi.org/10.1103/ PhysRevLett.102.040501. · DOI
  6. Larry Isenhower, Mark Saffman, and Klaus Molmer. Multibit C k NOT quantum gates via Rydberg blockade. Quantum Information Processing, 10(6):755-770, 2011. https:// doi.org/10.1007/s11128-011-0292-4. · DOI
  7. John Preskill. Quantum computing in the NISQ era and beyond. Quantum, 2:79, 2018. https: //doi.org/10.22331/q-2018-08-06-79. · DOI · Paper page
  8. Marco Cerezo, Andrew Arrasmith, Ryan Bab- bush, Simon C Benjamin, Suguru Endo, Keisuke Fujii, Jarrod R McClean, Kosuke Mi- tarai, Xiao Yuan, Lukasz Cincio, et al. Vari- ational quantum algorithms. Nature Reviews Physics, 3(9):625-644, 2021. https://doi. org/10.1038/s42254-021-00348-9. · DOI · Paper page
  9. Prakash Murali, Norbert Matthias Linke, Margaret Martonosi, Ali Javadi Abhari, Nhung Hong Nguyen, and Cinthia Huerta Alderete. Full-stack, real-system quan- tum computer studies: Architectural com- parisons and design insights. In 2019 ACM/IEEE 46th Annual International Symposium on Computer Architecture (ISCA), pages 527-540. IEEE, 2019. https: //doi.org/10.1145/3307650.3322273. · DOI · Paper page
  10. Edward Farhi, Jeffrey Goldstone, and Sam Gut- mann. A Quantum Approximate Optimization Algorithm. arXiv preprint arXiv:1411.4028, 2014. https://doi.org/10.48550/arXiv. 1411.4028. · DOI · Paper page
  11. Zain H Saleem, Teague Tomesh, Bilal Tariq, and Martin Suchara. Approaches to Con- strained Quantum Approximate Optimization. SN Computer Science, 4(2):183, 2023. https: //doi.org/10.1007/s42979-022-01638-4. · DOI
  12. Stuart Andrew Hadfield. Quantum Algorithms for Scientific Computing and Approximate Optimization. PhD thesis, Columbia Uni- versity, 2018. https://doi.org/10.7916/ D8X650C9. · DOI
  13. Stuart Hadfield, Zhihui Wang, Bryan O'Gorman, Eleanor G Rieffel, Davide Venturelli, and Ru- pak Biswas. From the quantum approximate optimization algorithm to a quantum alter- nating operator ansatz. Algorithms, 12(2):34, 2019. https://doi.org/10.3390/a12020034. · DOI · Paper page
  14. Zain Hamid Saleem. Max-independent set and the quantum alternating operator ansatz. International Journal of Quantum Information, 18(04):2050011, 2020. https://doi.org/10. 1142/S0219749920500112. · DOI · Paper page
  15. Adriano Barenco, Charles H Bennett, Richard Cleve, David P DiVincenzo, Norman Margo- lus, Peter Shor, Tycho Sleator, John A Smolin, and Harald Weinfurter. Elementary gates for quantum computation. Physical review A, 52 (5):3457, 1995. https://doi.org/10.1103/ PhysRevA.52.3457. · DOI · Paper page
  16. Juha J Vartiainen, Mikko Möttönen, and Martti M Salomaa. Efficient decomposition of quantum gates. Physical review letters, 92(17):177902, 2004. https://doi.org/10. 1103/PhysRevLett.92.177902. · DOI
  17. Esteban A Martinez, Thomas Monz, Daniel Nigg, Philipp Schindler, and Rainer Blatt. Compil- ing quantum algorithms for architectures with multi-qubit gates. New Journal of Physics, 18 (6):063029, 2016. https://doi.org/10.1088/ 1367-2630/18/6/063029. · DOI
  18. Pranav Gokhale, Jonathan M Baker, Casey Duckering, Natalie C Brown, Kenneth R Brown, and Frederic T Chong. Asymptotic improvements to quantum circuits via qutrits. In Proceedings of the 46th International Symposium on Computer Architecture, pages 554-566, 2019. https://doi.org/10.1145/ 3307650.3322253. · DOI · Paper page
  19. Péter Rakyta and Zoltán Zimborás. Approach- ing the theoretical limit in quantum gate de- composition. Quantum, 6:710, 2022. https: //doi.org/10.22331/q-2022-05-11-710. · DOI
  20. Chi-Kwong Li, Rebecca Roberts, and Xi- aoyan Yin. Decomposition of unitary ma- trices and quantum gates. International Journal of Quantum Information, 11(01): 1350015, 2013. https://doi.org/10.1142/ S0219749913500159. · DOI
  21. Ed Younis, Koushik Sen, Katherine Yelick, and Costin Iancu. QFAST: Conflating Search and Numerical Optimization for Scal- able Quantum Circuit Synthesis. In 2021 IEEE International Conference on Quantum Computing and Engineering (QCE), pages 232-243. IEEE, 2021. https://doi.org/10. 1109/QCE52317.2021.00041. · DOI
  22. Yunong Shi, Nelson Leung, Pranav Gokhale, Zane Rossi, David I Schuster, Henry Hoff- mann, and Frederic T Chong. Optimized Com- pilation of Aggregated Instructions for Real- istic Quantum Computers. In Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems, pages 1031-1044, 2019. https://doi.org/10.1145/ 3297858.3304018. · DOI
  23. Rebekah Herrman, Phillip C Lotshaw, James Os- trowski, Travis S Humble, and George Siop- sis. Multi-angle quantum approximate op- timization algorithm. Scientific Reports, 12 (1):1-10, 2022. https://doi.org/10.1038/ s41598-022-10555-8. · DOI
  24. Mark Saffman. Quantum computing with atomic qubits and Rydberg interactions: progress and challenges. Journal of Physics B: Atomic, Molecular and Optical Physics, 49(20):202001, 2016. https:doi.org/10.1088/0953-4075/ 49/20/202001. · DOI
  25. Juan Diego Arias Espinoza, Koen Groenland, Matteo Mazzanti, Kareljan Schoutens, and Rene Gerritsma. High-fidelity method for a single-step N -bit Toffoli gate in trapped ions. Physical Review A, 103(5):052437, 2021. https://doi.org/10.1103/PhysRevA. 103.052437. · DOI
  26. Or Katz, Marko Cetina, and Christopher Monroe. N -Body Interactions between Trapped Ion Qubits via Spin-Dependent Squeezing. Phys. Rev. Lett., 129:063603, Aug 2022. https://doi.org/10.1103/ PhysRevLett.129.063603. · DOI
  27. SE Rasmussen, K Groenland, R Gerritsma, K Schoutens, and NT Zinner. Single-step implementation of high-fidelity n-bit Toffoli gates. Physical Review A, 101(2):022308, 2020. https://doi.org/10.1103/PhysRevA. 101.022308. · DOI
  28. Yosep Kim, Alexis Morvan, Long B Nguyen, Ravi K Naik, Christian Jünger, Larry Chen, John Mark Kreikebaum, David I Santi- ago, and Irfan Siddiqi. High-fidelity three- qubit iToffoli gate for fixed-frequency super- conducting qubits. Nature Physics, pages 1-6, 2022. https://doi.org/10.1038/ s41567-022-01590-3. · DOI
  29. Alexis Morvan, VV Ramasesh, MS Blok, JM Kreikebaum, K O'Brien, L Chen, BK Mitchell, RK Naik, DI Santiago, and I Siddiqi. Qutrit Randomized Bench- marking. Physical review letters, 126(21): 210504, 2021. https://doi.org/10.1103/ PhysRevLett.126.210504. · DOI
  30. Pranav Gokhale, Ali Javadi-Abhari, Nathan Earnest, Yunong Shi, and Frederic T Chong. Optimized Quantum Compilation for Near- Term Algorithms with OpenPulse. In 2020 53rd Annual IEEE/ACM International Symposium on Microarchitecture (MICRO), pages 186-200. IEEE, 2020. https://doi. org/10.1109/MICRO50266.2020.00027. · DOI
  31. Lingling Lao, Prakash Murali, Margaret Martonosi, and Dan Browne. Designing Calibration and Expressivity-Efficient In- struction Sets for Quantum Computing. In 2021 ACM/IEEE 48th Annual International Symposium on Computer Architecture (ISCA), pages 846-859. IEEE, 2021. https:// doi.org/10.1109/ISCA52012.2021.00071. · DOI
  32. Daniel J Egger, Jakub Mareček, and Stefan Wo- erner. Warm-starting quantum optimization. Quantum, 5:479, 2021. https://doi.org/10. 22331/q-2021-06-17-479. · DOI · Paper page
  33. Teague Tomesh, Zain H Saleem, and Mar- tin Suchara. Quantum Local Search with the Quantum Alternating Operator Ansatz. Quantum, 6:781, 2022a. https://doi.org/ 10.22331/q-2022-08-22-781. · DOI
  34. Teague Tomesh, Zain H. Saleem, Michael A. Perlin, Pranav Gokhale, Martin Suchara, and Margaret Martonosi. Divide and Con- quer for Combinatorial Optimization and Dis- tributed Quantum Computation. In 2023 IEEE International Conference on Quantum Computing and Engineering (QCE), vol- ume 01, pages 1-12, 2023. https://doi.org/ 10.1109/QCE57702.2023.00009. · DOI
  35. Thomas G Draper, Samuel A Kutin, Eric M Rains, and Krysta M Svore. A logarithmic- depth quantum carry-lookahead adder. arXiv preprint quant-ph/0406142, 2004. https://doi.org/10.48550/arXiv. quant-ph/0406142. · DOI
  36. Amlan Chakrabarti and Susmita Sur-Kolay. De- signing quantum adder circuits and evaluating their error performance. In 2008 International Conference on Electronic Design, pages 1- 6. IEEE, 2008. https://doi.org/10.1109/ ICED.2008.4786689. · DOI
  37. Juan Miguel Arrazola, Olivia Di Matteo, Nicolás Quesada, Soran Jahangiri, Alain Delgado, and Nathan Killoran. Universal quantum circuits for quantum chemistry. Quantum, 6:742, 2022. https://doi.org/10.22331/ q-2022-06-20-742. · DOI
  38. Daniel Crow, Robert Joynt, and Mark Saffman. Improved Error Thresholds for Measurement- Free Error Correction. Physical review letters, 117(13):130503, 2016. https://doi.org/10. 1103/PhysRevLett.117.130503. · DOI
  39. Michael A. Perlin, Vickram N. Premakumar, Ji- akai Wang, Mark Saffman, and Robert Joynt. Fault-tolerant measurement-free quantum er- ror correction with multiqubit gates. Phys. Rev. A, 108:062426, Dec 2023. https://doi. org/10.1103/PhysRevA.108.062426. · DOI
  40. Raban Iten, Roger Colbeck, Ivan Kukuljan, Jonathan Home, and Matthias Christandl. Quantum circuits for isometries. Physical Review A, 93(3):032318, 2016. https://doi. org/10.1103/PhysRevA.93.032318. · DOI
  41. Teague Tomesh, Pranav Gokhale, Victory Omole, Gokul Subramanian Ravi, Kaitlin N Smith, Joshua Viszlai, Xin-Chuan Wu, Nikos Hardavellas, Margaret R Martonosi, and Frederic T Chong. SupermarQ: A Scalable Quantum Benchmark Suite. In 2022 IEEE International Symposium on High-Performance Computer Architecture (HPCA), pages 587-603. IEEE, 2022b. https://doi.org/10.1109/HPCA53966. 2022.00050. · DOI
  42. Google Quantum AI. Suppressing quantum errors by scaling a surface code logical qubit. Nature, 614(7949):676-681, 2023. See the supplemen- tary information for gate fidelities. https:// doi.org/10.1038/s41586-022-05434-1. · DOI · Paper page
  43. Jake Gulliksen, Durga Bhaktavatsala Rao Dasari, and Klaus Molmer. Characterization of how dissipation and dephasing errors accumu- late in quantum computers. EPJ Quantum Technology, 2(1):1-10, 2015. https://doi. org/10.1140/epjqt17. · DOI
  44. Ruslan Shaydulin, Phillip C. Lotshaw, Jeffrey Larson, James Ostrowski, and Travis S. Hum- ble. Parameter Transfer for Quantum Ap- proximate Optimization of Weighted MaxCut. ACM Transactions on Quantum Computing, 4 (3), April 2023. https://doi.org/10.1145/ 3584706. · DOI
  45. Joao Basso, Edward Farhi, Kunal Marwaha, Ben- jamin Villalonga, and Leo Zhou. The Quan- tum Approximate Optimization Algorithm at High Depth for MaxCut on Large-Girth Reg- ular Graphs and the Sherrington-Kirkpatrick Model. arXiv preprint arXiv:2110.14206, 2021. https://doi.org/10.48550/arXiv. 2110.14206. · DOI
  46. Ruslan Shaydulin, Changhao Li, Shouvanik Chakrabarti, Matthew DeCross, Dylan Her- man, Niraj Kumar, Jeffrey Larson, Danylo Lykov, Pierre Minssen, Yue Sun, et al. Evi- dence of scaling advantage for the quantum ap- proximate optimization algorithm on a classi- cally intractable problem. Science Advances, 10 (22):eadm6761, 2024. https://doi.org/10. 1126/sciadv.adm6761. · DOI · Paper page
  47. Angad Kalra, Faisal Qureshi, and Michael Tisi. Portfolio Asset Identification Using Graph Al- gorithms on a Quantum Annealer. Available at SSRN 3333537, 2018. https://dx.doi.org/ 10.2139/ssrn.3333537. · DOI
  48. Eugene L Lawler. Optimal Sequencing of a Single Machine Subject to Precedence Con- straints. Management science, 19(5):544-546, 1973. https://doi.org/10.1287/mnsc.19. 5.544. · DOI
  49. Andy Auyeung. A new phylogenetic tree model for fuzzy characters. In International Conference on Information Technology: Coding and Computing (ITCC'05)-Volume II, volume 1, pages 2-7. IEEE, 2005. https://doi.org/10.1109/ITCC.2005. · DOI
  50. Klaus Molmer, Larry Isenhower, and Mark Saffman. Efficient Grover search with Ry- dberg blockade. Journal of Physics B: Atomic, Molecular and Optical Physics, 44 (18):184016, 2011. https://doi.org/10. 1088/0953-4075/44/18/184016. · DOI
  51. David Petrosyan, Mark Saffman, and Klaus Molmer. Grover search algorithm with Rydberg-blockaded atoms: quantum Monte Carlo simulations. Journal of Physics B: Atomic, Molecular and Optical Physics, 49(9): 094004, 2016. http://dx.doi.org/10.1088/ 0953-4075/49/9/094004. · DOI
  52. Mohammadsadegh Khazali and Klaus Molmer. Fast multiqubit gates by adiabatic evolution in interacting excited-state manifolds of rydberg atoms and superconducting circuits. Physical Review X, 10(2):021054, 2020. https://doi. org/10.1103/PhysRevX.10.021054. · DOI
  53. Yao-Min Di and Hai-Rui Wei. Elementary gates for ternary quantum logic circuit. arXiv preprint arXiv:1105.5485, 2011. https://doi. org/10.48550/arXiv.1105.5485. · DOI

Cited by

Sorted by citations

Metadata

Authors
Tomesh, T., Allen, N., Dilley, D., & Saleem, Z.
Affiliations
  • Princeton University (US)
  • University of Waterloo (CA)
  • Argonne National Laboratory (US)
ORCID
Venue
arXiv
Publisher
arXiv
Published
2022
Volume
8
Pages
1493-1493
ISSN
2521-327X (ISSN-L)
DOI
10.48550/arxiv.2210.04378
arXiv
2210.04378
OpenAlex
W4403139636
Cited by
9
References
0
Citations by year
2026: 2 · 2025: 2 · 2024: 2 · 2023: 3
FWCI
0.88
Type
journal article
Language
en
Open access
Licence
Locations
  • Quantum (publishedVersion, cc-by)
  • arXiv (Cornell University) (submittedVersion)
  • DOAJ (DOAJ: Directory of Open Access Journals) (submittedVersion, cc-by-sa)
  • arXiv (Cornell University) (cc-by)
Funders
  • National Science Foundation (2037984, DE-AC02–06CH11357, 1730082)
  • U.S. Department of Energy (DE‐ AC02‐06CH11357, AC02‐06CH11357, 06CH11357, DE-AC02-)
  • University of Chicago (DE-AC02-06CH11357)
  • Office of Science (AC02‐06CH11357, DE-AC02, 06CH11357, DE-AC02-06CH11357)
  • Argonne National Laboratory (DE- AC02-06-CH11357, DE-AC02, AC02–06CH11357, 06CH11357)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
  • Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum Information and Cryptography
  • Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum many-body systems
Keywords
quantum gate decomposition, quantum approximate optimization algorithm, maximum independent set, variational quantum algorithms, hybrid quantum-classical algorithms, gate fidelity, constrained combinatorial optimization, near-term quantum devices

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review