Fast quantum circuit cutting with randomized measurements

Angus Lowe1,2, Matija Medvidović1,3,4, Anthony Hayes1, Lee J. O'Riordan1, Thomas R. Bromley1, Juan Miguel Arrazola1, and Nathan Killoran1

1Xanadu, Toronto, ON, M5G 2C8, Canada
2Center for Theoretical Physics, Massachusetts Institute of Technology, Cambridge, MA, 02139, USA
3Center for Computational Quantum Physics, Flatiron Institute, New York, NY, 10010, USA
4Department of Physics, Columbia University, New York, 10027, USA

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


We propose a new method to extend the size of a quantum computation beyond the number of physical qubits available on a single device. This is accomplished by randomly inserting measure-and-prepare channels to express the output state of a large circuit as a separable state across distinct devices. Our method employs randomized measurements, resulting in a sample overhead that is $\widetilde{O}(4^k / \varepsilon ^2)$, where $\varepsilon $ is the accuracy of the computation and $k$ the number of parallel wires that are "cut" to obtain smaller sub-circuits. We also show an information-theoretic lower bound of $\Omega(2^k / \varepsilon ^2)$ for any comparable procedure. We use our techniques to show that circuits in the Quantum Approximate Optimization Algorithm (QAOA) with $p$ entangling layers can be simulated by circuits on a fraction of the original number of qubits with an overhead that is roughly $2^{O(p\kappa)}$, where $\kappa$ is the size of a known balanced vertex separator of the graph which encodes the optimization problem. We obtain numerical evidence of practical speedups using our method applied to the QAOA, compared to prior work. Finally, we investigate the practical feasibility of applying the circuit cutting procedure to large-scale QAOA problems on clustered graphs by using a $30$-qubit simulator to evaluate the variational energy of a $129$-qubit problem as well as carry out a $62$-qubit optimization.

► BibTeX data

► References

[1] https:/​/​​XanaduAI/​randomized-measurements-circuit-cutting (2022).

[2] Scott Aaronsonand Daniel Gottesman ``Improved simulation of stabilizer circuits'' Phys. Rev. A 70, 052328 (2004).

[3] J. Avron, Ofer Casper, and Ilan Rozen, ``Quantum advantage and noise reduction in distributed quantum computing'' Phys. Rev. A 104, 052404 (2021).

[4] Thomas Ayral, François-Marie Le Régent, Zain Saleem, Yuri Alexeev, and Martin Suchara, ``Quantum Divide and Compute: Hardware Demonstrations and Noisy Simulations'' 2020 IEEE Computer Society Annual Symposium on VLSI (ISVLSI) 138–140 (2020).

[5] F. Barratt, James Dborin, Matthias Bal, Vid Stojevic, Frank Pollmann, and A. G. Green, ``Parallel quantum simulation of large systems on small NISQ computers'' npj Quantum Information 7, 79 (2021).

[6] Ville Bergholm, Josh Izaac, Maria Schuld, Christian Gogolin, Shahnawaz Ahmed, Vishnu Ajith, M. Sohaib Alam, Guillermo Alonso-Linaje, B. AkashNarayanan, Ali Asadi, Juan Miguel Arrazola, Utkarsh Azad, Sam Banning, Carsten Blank, Thomas R Bromley, Benjamin A. Cordier, Jack Ceroni, Alain Delgado, Olivia Di Matteo, Amintor Dusko, Tanya Garg, Diego Guala, Anthony Hayes, Ryan Hill, Aroosa Ijaz, Theodor Isacsson, David Ittah, Soran Jahangiri, Prateek Jain, Edward Jiang, Ankit Khandelwal, Korbinian Kottmann, Robert A. Lang, Christina Lee, Thomas Loke, Angus Lowe, Keri McKiernan, Johannes Jakob Meyer, J. A. Montañez-Barrera, Romain Moyard, Zeyue Niu, Lee James O'Riordan, Steven Oud, Ashish Panigrahi, Chae-Yeun Park, Daniel Polatajko, Nicolás Quesada, Chase Roberts, Nahum Sá, Isidor Schoch, Borun Shi, Shuli Shu, Sukin Sim, Arshpreet Singh, Ingrid Strandberg, Jay Soni, Antal Száva, Slimane Thabet, Rodrigo A. Vargas-Hernández, Trevor Vincent, Nicola Vitucci, Maurice Weber, David Wierichs, Roeland Wiersema, Moritz Willmann, Vincent Wong, Shaoming Zhang, and Nathan Killoran, ``PennyLane: Automatic differentiation of hybrid quantum-classical computations'' (2018).

[7] Sergey Bravyiand David Gosset ``Improved Classical Simulation of Quantum Circuits Dominated by Clifford Gates'' Phys. Rev. Lett. 116, 250501 (2016).

[8] Sergey Bravyi, David Gosset, and Ramis Movassagh, ``Classical algorithms for quantum mean values'' Nature Physics 17, 337–341 (2021).

[9] Sergey Bravyi, Graeme Smith, and John A. Smolin, ``Trading Classical and Quantum Computational Resources'' Phys. Rev. X 6, 021043 (2016).

[10] Sergey Bravyi, Alexander Kliesch, Robert Koenig, and Eugene Tang, ``Obstacles to Variational Quantum Optimization from Symmetry Protection'' Phys. Rev. Lett. 125, 260505 (2020).

[11] Sergey Bravyi, Dan Browne, Padraic Calpin, Earl Campbell, David Gosset, and Mark Howard, ``Simulation of quantum circuits by low-rank stabilizer decompositions'' Quantum 3, 181 (2019).

[12] Thang Nguyen Buiand Curt Jones ``Finding good approximate vertex and edge partitions is NP-hard'' Information Processing Letters 42, 153–159 (1992).

[13] Francesco Buscemiand Nilanjana Datta ``The Quantum Capacity of Channels With Arbitrarily Correlated Noise'' IEEE Transactions on Information Theory 56, 1447–1460 (2010).

[14] Senrui Chen, Wenjun Yu, Pei Zeng, and Steven T. Flammia, ``Robust Shadow Estimation'' PRX Quantum 2, 030348 (2021).

[15] Andrew M. Childs, Yuan Su, Minh C. Tran, Nathan Wiebe, and Shuchen Zhu, ``Theory of Trotter Error with Commutator Scaling'' Physical Review X 11 (2021).

[16] Thomas M. Coverand Joy A. Thomas ``Elements of Information Theory'' Wiley (2005).

[17] Vedran Dunjko, Yimin Ge, and J. Ignacio Cirac, ``Computational Speedups Using Small Quantum Devices'' Phys. Rev. Lett. 121, 250501 (2018).

[18] Andreas Elben, Steven T. Flammia, Hsin-Yuan Huang, Richard Kueng, John Preskill, Benoît Vermersch, and Peter Zoller, ``The randomized measurement toolbox'' (2022).

[19] Leo Fang, Andreas Hehn, Harun Bayraktar, and Sam Stanwyck, ``NVIDIA/​cuQuantum: cuQuantum v22.05.0'' (2022).

[20] Robert M. Fano ``Transmission of Information: a Statistical Theory of Communications'' MIT Press (1966).

[21] Edward Farhi, David Gamarnik, and Sam Gutmann, ``The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: A Typical Case'' (2020).

[22] Edward Farhi, David Gamarnik, and Sam Gutmann, ``The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: Worst Case Examples'' (2020).

[23] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann, ``A Quantum Approximate Optimization Algorithm'' (2014).

[24] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann, ``A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem'' (2014).

[25] Edward Farhiand Aram W Harrow ``Quantum Supremacy through the Quantum Approximate Optimization Algorithm'' (2016).

[26] Uriel Feige, MohammadTaghi Hajiaghayi, and James R. Lee, ``Improved Approximation Algorithms for Minimum Weight Vertex Separators'' SIAM Journal on Computing 38, 629–657 (2008).

[27] Johnnie Grayand Stefanos Kourtis ``Hyper-optimized tensor network contraction'' Quantum 5, 410 (2021).

[28] M Guţă, J Kahn, R Kueng, and J A Tropp, ``Fast state tomography with optimal error bounds'' Journal of Physics A: Mathematical and Theoretical 53, 204001 (2020).

[29] Jeongwan Haah, Aram W. Harrow, Zhengfeng Ji, Xiaodi Wu, and Nengkun Yu, ``Sample-Optimal Tomography of Quantum States'' IEEE Transactions on Information Theory 63, 5628–5641 (2017).

[30] Stuart Hadfield, Zhihui Wang, Bryan O’Gorman, Eleanor G. Rieffel, Davide Venturelli, and Rupak Biswas, ``From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz'' Algorithms 12 (2019).

[31] Michael Horodecki, Peter W. Shor, and Mary Beth Ruskai, ``Entanglement Breaking Channels'' Reviews in Mathematical Physics 15, 629–641 (2003).

[32] Hsin-Yuan Huang, Richard Kueng, and John Preskill, ``Predicting many properties of a quantum system from very few measurements'' Nature Physics 16, 1050–1057 (2020).

[33] William Huggins, Piyush Patil, Bradley Mitchell, K Birgitta Whaley, and E Miles Stoudenmire, ``Towards quantum machine learning with tensor networks'' Quantum Science and Technology 4, 024001 (2019).

[34] Richard Kuengand David Gross ``Qubit stabilizer states are complex projective 3-designs'' (2015).

[35] Junde Li, Mahabubul Alam, and Swaroop Ghosh, ``Large-scale Quantum Approximate Optimization via Divide-and-Conquer'' (2021).

[36] Seth Lloyd, Maria Schuld, Aroosa Ijaz, Josh Izaac, and Nathan Killoran, ``Quantum embeddings for machine learning'' (2020).

[37] Angus Loweand Ashwin Nayak ``Lower bounds for learning quantum states with single-copy measurements'' (2022).

[38] Danylo Lykov, Jonathan Wurtz, Cody Poole, Mark Saffman, Tom Noel, and Yuri Alexeev, ``Sampling Frequency Thresholds for Quantum Advantage of Quantum Approximate Optimization Algorithm'' (2022).

[39] Igor L. Markovand Yaoyun Shi ``Simulating Quantum Computation by Contracting Tensor Networks'' SIAM Journal on Computing 38, 963–981 (2008).

[40] Simon C. Marshall, Casper Gyurik, and Vedran Dunjko, ``High Dimensional Quantum Machine Learning With Small Quantum Computers'' (2022).

[41] Matija Medvidovićand Giuseppe Carleo ``Classical variational simulation of the Quantum Approximate Optimization Algorithm'' npj Quantum Information 7 (2021).

[42] Kosuke Mitaraiand Keisuke Fujii ``Constructing a virtual two-qubit gate by sampling single-qubit operations'' New Journal of Physics 23, 023021 (2021).

[43] Kosuke Mitaraiand Keisuke Fujii ``Overhead for simulating a non-local channel with local channels by quasiprobability sampling'' Quantum 5, 388 (2021).

[44] Philipp Moritz, Robert Nishihara, Stephanie Wang, Alexey Tumanov, Richard Liaw, Eric Liang, Melih Elibol, Zongheng Yang, William Paul, Michael I. Jordan, and Ion Stoica, ``Ray: A Distributed Framework for Emerging AI Applications'' (2017).

[45] Hakop Pashayan, Joel J. Wallman, and Stephen D. Bartlett, ``Estimating Outcome Probabilities of Quantum Circuits Using Quasiprobabilities'' Phys. Rev. Lett. 115, 070501 (2015).

[46] Tianyi Peng, Aram W. Harrow, Maris Ozols, and Xiaodi Wu, ``Simulating Large Quantum Circuits on a Small Quantum Computer'' Physical Review Letters 125 (2020).

[47] Michael A. Perlin, Zain H. Saleem, Martin Suchara, and James C. Osborn, ``Quantum circuit cutting with maximum-likelihood tomography'' npj Quantum Information 7 (2021).

[48] Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man-Hong Yung, Xiao-Qi Zhou, Peter J. Love, Alán Aspuru-Guzik, and Jeremy L. O'Brien, ``A variational eigenvalue solver on a photonic quantum processor'' Nature Communications 5 (2014).

[49] Christophe Piveteauand David Sutter ``Circuit knitting with classical communication'' (2022).

[50] Zain H. Saleem, Teague Tomesh, Michael A. Perlin, Pranav Gokhale, and Martin Suchara, ``Quantum Divide and Conquer for Combinatorial Optimization and Distributed Computing'' (2021).

[51] Igal Sasonand Sergio Verdú ``$f$ -Divergence Inequalities'' IEEE Transactions on Information Theory 62, 5973–6006 (2016).

[52] Maria Schuld, Alex Bocharov, Krysta M. Svore, and Nathan Wiebe, ``Circuit-centric quantum classifiers'' Physical Review A 101 (2020).

[53] Maria Schuld, Ville Bergholm, Christian Gogolin, Josh Izaac, and Nathan Killoran, ``Evaluating analytic gradients on quantum hardware'' Phys. Rev. A 99, 032331 (2019).

[54] Hayk Shoukourian, Torsten Wilde, Axel Auweter, and Arndt Bode, ``Predicting the energy and power consumption of strong and weak scaling HPC applications'' Supercomputing Frontiers and Innovations 1, 20–41 (2014).

[55] Wei Tangand Margaret Martonosi ``ScaleQC: A Scalable Framework for Hybrid Computation on Quantum and Classical Processors'' (2022).

[56] Ewout Van Den Berg ``A simple method for sampling random Clifford operators'' 2021 IEEE International Conference on Quantum Computing and Engineering (QCE) 54–59 (2021).

[57] Zhihui Wang, Stuart Hadfield, Zhang Jiang, and Eleanor G. Rieffel, ``Quantum approximate optimization algorithm for MaxCut: A fermionic view'' Phys. Rev. A 97, 022304 (2018).

[58] John Watrous ``The Theory of Quantum Information'' Cambridge University Press (2018).

[59] Zak Webb ``The Clifford group forms a unitary 3-design'' (2015).

[60] Roeland Wiersema, Leonardo Guerini, Juan Felipe Carrasquilla, and Leandro Aolita, ``Circuit connectivity boosts by quantum-classical-quantum interfaces'' (2022).

[61] Xiao Yuan, Jinzhao Sun, Junyu Liu, Qi Zhao, and You Zhou, ``Quantum Simulation with Hybrid Tensor Networks'' Phys. Rev. Lett. 127, 040501 (2021).

[62] Huangjun Zhu ``Multiqubit Clifford groups are unitary 3-designs'' Phys. Rev. A 96, 062336 (2017).

Cited by

[1] Massimiliano Incudini, Michele Grossi, Andrea Ceschini, Antonio Mandarino, Massimo Panella, Sofia Vallecorsa, and David Windridge, "Resource saving via ensemble techniques for quantum neural networks", Quantum Machine Intelligence 5 2, 39 (2023).

[2] Christian Ufrecht, Maniraman Periyasamy, Sebastian Rietsch, Daniel D. Scherer, Axel Plinge, and Christopher Mutschler, "Cutting multi-control quantum gates with ZX calculus", Quantum 7, 1147 (2023).

[3] Matthew DeCross, Eli Chertkov, Megan Kohagen, and Michael Foss-Feig, "Qubit-Reuse Compilation with Mid-Circuit Measurement and Reset", Physical Review X 13 4, 041057 (2023).

[4] Lukas Brenner, Christophe Piveteau, and David Sutter, "Optimal wire cutting with classical communication", arXiv:2302.03366, (2023).

[5] Travis L. Scholten, Carl J. Williams, Dustin Moody, Michele Mosca, William Hurley, William J. Zeng, Matthias Troyer, and Jay M. Gambetta, "Assessing the Benefits and Risks of Quantum Computers", arXiv:2401.16317, (2024).

[6] Lirandë Pira and Chris Ferrie, "An Invitation to Distributed Quantum Neural Networks", arXiv:2211.07056, (2022).

[7] Marvin Bechtold, Johanna Barzen, Frank Leymann, Alexander Mandl, Julian Obst, Felix Truger, and Benjamin Weder, "Investigating the effect of circuit cutting in QAOA for the MaxCut problem on NISQ devices", Quantum Science and Technology 8 4, 045022 (2023).

[8] Junpeng Zhan, "Variational Quantum Search with Shallow Depth for Unstructured Database Search", arXiv:2212.09505, (2022).

[9] Daniel T. Chen, Ethan H. Hansen, Xinpeng Li, Vinooth Kulkarni, Vipin Chaudhary, Bin Ren, Qiang Guan, Sanmukh Kuppannagari, Ji Liu, and Shuai Xu, "Efficient Quantum Circuit Cutting by Neglecting Basis Elements", arXiv:2304.04093, (2023).

[10] Filipa C. R. Peres and Ernesto F. Galvão, "Quantum circuit compilation and hybrid computation using Pauli-based computation", Quantum 7, 1126 (2023).

[11] Lukas Schmitt, Christophe Piveteau, and David Sutter, "Cutting circuits with multiple two-qubit unitaries", arXiv:2312.11638, (2023).

[12] Harun Bayraktar, Ali Charara, David Clark, Saul Cohen, Timothy Costa, Yao-Lung L. Fang, Yang Gao, Jack Guan, John Gunnels, Azzam Haidar, Andreas Hehn, Markus Hohnerbach, Matthew Jones, Tom Lubowe, Dmitry Lyakh, Shinya Morino, Paul Springer, Sam Stanwyck, Igor Terentyev, Satya Varadhan, Jonathan Wong, and Takuma Yamaguchi, "cuQuantum SDK: A High-Performance Library for Accelerating Quantum Science", arXiv:2308.01999, (2023).

[13] Diego Guala, Shaoming Zhang, Esther Cruz, Carlos A. Riofrío, Johannes Klepsch, and Juan Miguel Arrazola, "Practical overview of image classification with tensor-network quantum circuits", Scientific Reports 13, 4427 (2023).

[14] Ritajit Majumdar and Christopher J. Wood, "Error mitigated quantum circuit cutting", arXiv:2211.13431, (2022).

[15] Daniel T. Chen, Ethan H. Hansen, Xinpeng Li, Aaron Orenstein, Vinooth Kulkarni, Vipin Chaudhary, Qiang Guan, Ji Liu, Yang Zhang, and Shuai Xu, "Online Detection of Golden Circuit Cutting Points", arXiv:2308.10153, (2023).

[16] Carlos A. Riofrío, Oliver Mitevski, Caitlin Jones, Florian Krellner, Aleksandar Vučković, Joseph Doetsch, Johannes Klepsch, Thomas Ehmer, and Andre Luckow, "A performance characterization of quantum generative models", arXiv:2301.09363, (2023).

[17] Daniel T. Chen, Zain H. Saleem, and Michael A. Perlin, "Quantum Divide and Conquer for Classical Shadows", arXiv:2212.00761, (2022).

[18] Massimiliano Incudini, Michele Grossi, Andrea Ceschini, Antonio Mandarino, Massimo Panella, Sofia Vallecorsa, and David Windridge, "Resource Saving via Ensemble Techniques for Quantum Neural Networks", arXiv:2303.11283, (2023).

[19] Gideon Uchehara, Tor M. Aamodt, and Olivia Di Matteo, "Rotation-inspired circuit cut optimization", arXiv:2211.07358, (2022).

[20] Hasini Witharana, Daniel Volya, and Prabhat Mishra, "quAssert: Automatic Generation of Quantum Assertions", arXiv:2303.01487, (2023).

[21] Ryo Nagai, Shu Kanno, Yuki Sato, and Naoki Yamamoto, "Quantum channel decomposition with preselection and postselection", Physical Review A 108 2, 022615 (2023).

[22] Hang Lian, Jinchen Xu, Yu Zhu, Zhiqiang Fan, Yi Liu, and Zheng Shan, "Fast reconstruction algorithm based on HMC sampling", Scientific Reports 13, 17773 (2023).

The above citations are from Crossref's cited-by service (last updated successfully 2024-01-18 07:02:13) and SAO/NASA ADS (last updated successfully 2024-03-02 10:10:53). The list may be incomplete as not all publishers provide suitable and complete citation data.

Could not fetch Crossref cited-by data during last attempt 2024-03-02 10:10:50: Encountered the unhandled forward link type postedcontent_cite while looking for citations to DOI 10.22331/q-2023-03-02-934.