Fast quantum circuit cutting with randomized measurements

Fast quantum circuit cutting with randomized measurements

Fast quantum circuit cutting with randomized measurements PlatoBlockchain Data Intelligence. Vertical Search. Ai.

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.

Abstract

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(pkappa)}$, 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:/​/​github.com/​XanaduAI/​randomized-measurements-circuit-cutting (2022).
https:/​/​github.com/​XanaduAI/​randomized-measurements-circuit-cutting

[2] Scott Aaronsonand Daniel Gottesman “Improved simulation of stabilizer circuits” Phys. Rev. A 70, 052328 (2004).
https:/​/​doi.org/​10.1103/​PhysRevA.70.052328

[3] J. Avron, Ofer Casper, and Ilan Rozen, “Quantum advantage and noise reduction in distributed quantum computing” Phys. Rev. A 104, 052404 (2021).
https:/​/​doi.org/​10.1103/​PhysRevA.104.052404

[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).
https:/​/​doi.org/​10.1109/​ISVLSI49217.2020.00034

[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).
https:/​/​doi.org/​10.1038/​s41534-021-00420-3

[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).
https:/​/​doi.org/​10.48550/​ARXIV.1811.04968
https:/​/​arxiv.org/​abs/​1811.04968

[7] Sergey Bravyiand David Gosset “Improved Classical Simulation of Quantum Circuits Dominated by Clifford Gates” Phys. Rev. Lett. 116, 250501 (2016).
https:/​/​doi.org/​10.1103/​PhysRevLett.116.250501

[8] Sergey Bravyi, David Gosset, and Ramis Movassagh, “Classical algorithms for quantum mean values” Nature Physics 17, 337–341 (2021).
https:/​/​doi.org/​10.1038/​s41567-020-01109-8

[9] Sergey Bravyi, Graeme Smith, and John A. Smolin, “Trading Classical and Quantum Computational Resources” Phys. Rev. X 6, 021043 (2016).
https:/​/​doi.org/​10.1103/​PhysRevX.6.021043

[10] Sergey Bravyi, Alexander Kliesch, Robert Koenig, and Eugene Tang, “Obstacles to Variational Quantum Optimization from Symmetry Protection” Phys. Rev. Lett. 125, 260505 (2020).
https:/​/​doi.org/​10.1103/​PhysRevLett.125.260505

[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).
https:/​/​doi.org/​10.22331/​q-2019-09-02-181

[12] Thang Nguyen Buiand Curt Jones “Finding good approximate vertex and edge partitions is NP-hard” Information Processing Letters 42, 153–159 (1992).
https:/​/​doi.org/​10.1016/​0020-0190(92)90140-Q
https:/​/​www.sciencedirect.com/​science/​article/​pii/​002001909290140Q

[13] Francesco Buscemiand Nilanjana Datta “The Quantum Capacity of Channels With Arbitrarily Correlated Noise” IEEE Transactions on Information Theory 56, 1447–1460 (2010).
https:/​/​doi.org/​10.1109/​TIT.2009.2039166

[14] Senrui Chen, Wenjun Yu, Pei Zeng, and Steven T. Flammia, “Robust Shadow Estimation” PRX Quantum 2, 030348 (2021).
https:/​/​doi.org/​10.1103/​PRXQuantum.2.030348

[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).
https:/​/​doi.org/​10.1103/​physrevx.11.011020

[16] Thomas M. Coverand Joy A. Thomas “Elements of Information Theory” Wiley (2005).
https:/​/​doi.org/​10.1002/​047174882x

[17] Vedran Dunjko, Yimin Ge, and J. Ignacio Cirac, “Computational Speedups Using Small Quantum Devices” Phys. Rev. Lett. 121, 250501 (2018).
https:/​/​doi.org/​10.1103/​PhysRevLett.121.250501

[18] Andreas Elben, Steven T. Flammia, Hsin-Yuan Huang, Richard Kueng, John Preskill, Benoît Vermersch, and Peter Zoller, “The randomized measurement toolbox” (2022).
https:/​/​doi.org/​10.48550/​ARXIV.2203.11374
https:/​/​arxiv.org/​abs/​2203.11374

[19] Leo Fang, Andreas Hehn, Harun Bayraktar, and Sam Stanwyck, “NVIDIA/​cuQuantum: cuQuantum v22.05.0” (2022).
https:/​/​doi.org/​10.5281/​zenodo.6574510

[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).
https:/​/​doi.org/​10.48550/​ARXIV.2004.09002
https:/​/​arxiv.org/​abs/​2004.09002

[22] Edward Farhi, David Gamarnik, and Sam Gutmann, “The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: Worst Case Examples” (2020).
https:/​/​doi.org/​10.48550/​ARXIV.2005.08747
https:/​/​arxiv.org/​abs/​2005.08747

[23] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann, “A Quantum Approximate Optimization Algorithm” (2014).
https:/​/​doi.org/​10.48550/​ARXIV.1411.4028
https:/​/​arxiv.org/​abs/​1411.4028

[24] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann, “A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem” (2014).
https:/​/​doi.org/​10.48550/​ARXIV.1412.6062
https:/​/​arxiv.org/​abs/​1412.6062

[25] Edward Farhiand Aram W Harrow “Quantum Supremacy through the Quantum Approximate Optimization Algorithm” (2016).
https:/​/​doi.org/​10.48550/​ARXIV.1602.07674
https:/​/​arxiv.org/​abs/​1602.07674

[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).
https:/​/​doi.org/​10.1137/​05064299X

[27] Johnnie Grayand Stefanos Kourtis “Hyper-optimized tensor network contraction” Quantum 5, 410 (2021).
https:/​/​doi.org/​10.22331/​q-2021-03-15-410

[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).
https:/​/​doi.org/​10.1088/​1751-8121/​ab8111

[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).
https:/​/​doi.org/​10.1109/​TIT.2017.2719044

[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).
https:/​/​doi.org/​10.3390/​a12020034
https:/​/​www.mdpi.com/​1999-4893/​12/​2/​34

[31] Michael Horodecki, Peter W. Shor, and Mary Beth Ruskai, “Entanglement Breaking Channels” Reviews in Mathematical Physics 15, 629–641 (2003).
https:/​/​doi.org/​10.1142/​S0129055X03001709

[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).
https:/​/​doi.org/​10.1038/​s41567-020-0932-7

[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).
https:/​/​doi.org/​10.1088/​2058-9565/​aaea94

[34] Richard Kuengand David Gross “Qubit stabilizer states are complex projective 3-designs” (2015).
https:/​/​doi.org/​10.48550/​ARXIV.1510.02767
https:/​/​arxiv.org/​abs/​1510.02767

[35] Junde Li, Mahabubul Alam, and Swaroop Ghosh, “Large-scale Quantum Approximate Optimization via Divide-and-Conquer” (2021).
https:/​/​doi.org/​10.48550/​ARXIV.2102.13288
https:/​/​arxiv.org/​abs/​2102.13288

[36] Seth Lloyd, Maria Schuld, Aroosa Ijaz, Josh Izaac, and Nathan Killoran, “Quantum embeddings for machine learning” (2020).
https:/​/​doi.org/​10.48550/​ARXIV.2001.03622
https:/​/​arxiv.org/​abs/​2001.03622

[37] Angus Loweand Ashwin Nayak “Lower bounds for learning quantum states with single-copy measurements” (2022).
https:/​/​doi.org/​10.48550/​ARXIV.2207.14438
https:/​/​arxiv.org/​abs/​2207.14438

[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).
https:/​/​doi.org/​10.48550/​ARXIV.2206.03579
https:/​/​arxiv.org/​abs/​2206.03579

[39] Igor L. Markovand Yaoyun Shi “Simulating Quantum Computation by Contracting Tensor Networks” SIAM Journal on Computing 38, 963–981 (2008).
https:/​/​doi.org/​10.1137/​050644756

[40] Simon C. Marshall, Casper Gyurik, and Vedran Dunjko, “High Dimensional Quantum Machine Learning With Small Quantum Computers” (2022).
https:/​/​doi.org/​10.48550/​ARXIV.2203.13739
https:/​/​arxiv.org/​abs/​2203.13739

[41] Matija Medvidovićand Giuseppe Carleo “Classical variational simulation of the Quantum Approximate Optimization Algorithm” npj Quantum Information 7 (2021).
https:/​/​doi.org/​10.1038/​s41534-021-00440-z

[42] Kosuke Mitaraiand Keisuke Fujii “Constructing a virtual two-qubit gate by sampling single-qubit operations” New Journal of Physics 23, 023021 (2021).
https:/​/​doi.org/​10.1088/​1367-2630/​abd7bc

[43] Kosuke Mitaraiand Keisuke Fujii “Overhead for simulating a non-local channel with local channels by quasiprobability sampling” Quantum 5, 388 (2021).
https:/​/​doi.org/​10.22331/​q-2021-01-28-388

[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).
https:/​/​doi.org/​10.48550/​ARXIV.1712.05889
https:/​/​arxiv.org/​abs/​1712.05889

[45] Hakop Pashayan, Joel J. Wallman, and Stephen D. Bartlett, “Estimating Outcome Probabilities of Quantum Circuits Using Quasiprobabilities” Phys. Rev. Lett. 115, 070501 (2015).
https:/​/​doi.org/​10.1103/​PhysRevLett.115.070501

[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).
https:/​/​doi.org/​10.1103/​physrevlett.125.150504

[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).
https:/​/​doi.org/​10.1038/​s41534-021-00390-6

[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).
https:/​/​doi.org/​10.1038/​ncomms5213

[49] Christophe Piveteauand David Sutter “Circuit knitting with classical communication” (2022).
https:/​/​doi.org/​10.48550/​ARXIV.2205.00016
https:/​/​arxiv.org/​abs/​2205.00016

[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).
arXiv:2107.07532

[51] Igal Sasonand Sergio Verdú “$f$ -Divergence Inequalities” IEEE Transactions on Information Theory 62, 5973–6006 (2016).
https:/​/​doi.org/​10.1109/​TIT.2016.2603151

[52] Maria Schuld, Alex Bocharov, Krysta M. Svore, and Nathan Wiebe, “Circuit-centric quantum classifiers” Physical Review A 101 (2020).
https:/​/​doi.org/​10.1103/​physreva.101.032308

[53] Maria Schuld, Ville Bergholm, Christian Gogolin, Josh Izaac, and Nathan Killoran, “Evaluating analytic gradients on quantum hardware” Phys. Rev. A 99, 032331 (2019).
https:/​/​doi.org/​10.1103/​PhysRevA.99.032331

[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).
https:/​/​doi.org/​10.14529/​jsfi140202

[55] Wei Tangand Margaret Martonosi “ScaleQC: A Scalable Framework for Hybrid Computation on Quantum and Classical Processors” (2022).
https:/​/​doi.org/​10.48550/​ARXIV.2207.00933
https:/​/​arxiv.org/​abs/​2207.00933

[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).
https:/​/​doi.org/​10.1109/​QCE52317.2021.00021

[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).
https:/​/​doi.org/​10.1103/​PhysRevA.97.022304

[58] John Watrous “The Theory of Quantum Information” Cambridge University Press (2018).
https:/​/​doi.org/​10.1017/​9781316848142

[59] Zak Webb “The Clifford group forms a unitary 3-design” (2015).
https:/​/​doi.org/​10.48550/​ARXIV.1510.02769
https:/​/​arxiv.org/​abs/​1510.02769

[60] Roeland Wiersema, Leonardo Guerini, Juan Felipe Carrasquilla, and Leandro Aolita, “Circuit connectivity boosts by quantum-classical-quantum interfaces” (2022).
https:/​/​doi.org/​10.48550/​ARXIV.2203.04984
https:/​/​arxiv.org/​abs/​2203.04984

[61] Xiao Yuan, Jinzhao Sun, Junyu Liu, Qi Zhao, and You Zhou, “Quantum Simulation with Hybrid Tensor Networks” Phys. Rev. Lett. 127, 040501 (2021).
https:/​/​doi.org/​10.1103/​PhysRevLett.127.040501

[62] Huangjun Zhu “Multiqubit Clifford groups are unitary 3-designs” Phys. Rev. A 96, 062336 (2017).
https:/​/​doi.org/​10.1103/​PhysRevA.96.062336

Cited by

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

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

[3] Matthew DeCross, Eli Chertkov, Megan Kohagen, and Michael Foss-Feig, “Qubit-reuse compilation with mid-circuit measurement and reset”, arXiv:2210.08039, (2022).

[4] Christian Ufrecht, Maniraman Periyasamy, Sebastian Rietsch, Daniel D. Scherer, Axel Plinge, and Christopher Mutschler, “Cutting multi-control quantum gates with ZX calculus”, arXiv:2302.00387, (2023).

[5] 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”, arXiv:2302.01792, (2023).

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

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

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

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

[10] Diego Guala, Shaoming Zhang, Esther Cruz, Carlos A. Riofrío, Johannes Klepsch, and Juan Miguel Arrazola, “A practical overview of image classification with variational tensor-network quantum circuits”, arXiv:2209.11058, (2022).

The above citations are from SAO/NASA ADS (last updated successfully 2023-03-03 16:49:02). 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-03-03 16:49:00).

Time Stamp:

More from Quantum Journal