Yipeng Huang
Steven Holtzen
Todd Millstein
ABSTRACT
Due to the unreliability and limited capacity of existing quantum computer prototypes, quantum circuit simulation continues to be a vital tool for validating next generation quantum computers and for studying variational quantum algorithms, which are among the leading candidates for useful quantum computation. Existing quantum circuit simulators do not address the common traits of variational algorithms, namely: 1) their ability to work with noisy qubits and operations, 2) their repeated execution of the same circuits but with different parameters, and 3) the fact that they sample from circuit final wavefunctions to drive a classical optimization routine. We present a quantum circuit simulation toolchain based on logical abstractions targeted for simulating variational algorithms. Our proposed toolchain encodes quantum amplitudes and noise probabilities in a probabilistic graphical model, and it compiles the circuits to logical formulas that support efficient repeated simulation of and sampling from quantum circuits for different parameters. Compared to state-of-the-art state vector and density matrix quantum circuit simulators, our simulation approach offers greater performance when sampling from noisy circuits with at least eight to 20 qubits and with around 12 operations on each qubit, making the approach ideal for simulating near-term variational quantum algorithms. And for simulating noise-free shallow quantum circuits with 32 qubits, our simulation approach offers a 66× reduction in sampling cost versus quantum circuit simulation techniques based on tensor network contraction.
- 1642293.1642501 Mark Chavira and Adnan Darwiche. 2006. Encoding CNFs to Empower Com-Google Scholar
- ponent Analysis. In Theory and Applications of Satis ability Testing-SAT 2006,Google Scholar
- delberg, 61-74. Mark Chavira and Adnan Darwiche. 2008. On Probabilistic Inference by WeightedGoogle Scholar
- Model Counting. Artif. Intell. 172, 6-7 ( April 2008 ), 772-799. https://doi.org/10.Google Scholar
- 1016/j.artint. 2007. 11. 002 Siddhartha Chib and Edward Greenberg. 1995. Understanding the Metropolis-Google Scholar
- Hastings algorithm. The american statistician 49, 4 ( 1995 ), 327-335. YooJung Choi, Antonio Vergari, and Guy Van den Broeck. 2020. ProbabilisticGoogle Scholar
- Circuits: A Unifying Framework for Tractable Probabilistic Models. ( 2020 ). John F. Clauser, Michael A. Horne, Abner Shimony, and Richard A. Holt. 1969.Google Scholar
- Proposed Experiment to Test Local Hidden-Variable Theories. Phys. Rev. Lett. 23Google Scholar
- (Oct 1969 ), 880-884. Issue 15. https://doi.org/10.1103/PhysRevLett.23. 880 Andrew W. Cross, Lev S. Bishop, Sarah Sheldon, Paul D. Nation, and Jay M.Google Scholar
- Gambetta. 2019. Validating quantum computers using randomized model circuits.Google Scholar
- Phys. Rev. A 100 ( Sep 2019 ), 032328. Issue 3. https://doi.org/10.1103/PhysRevA. Google ScholarCross Ref
- 100.032328 Adnan Darwiche. 2002. A Logical Approach to Factoring Belief Networks. InGoogle Scholar
- Representation and Reasoning (Toulouse, France) (KR'02). Morgan KaufmannGoogle Scholar
- Publishers Inc., San Francisco, CA, USA, 409-420. http://dl.acm.org/citation.Google Scholar
- cfm?id=3087093.3087128 Adnan Darwiche. 2003. A Di erential Approach to Inference in Bayesian Net-Google Scholar
- works. J. ACM 50, 3 (May 2003 ), 280-305. https://doi.org/10.1145/765568.765570 Adnan Darwiche. 2009. Modeling and Reasoning with Bayesian Networks (1st ed.).Google ScholarDigital Library
- Cambridge University Press, New York, NY, USA. Adnan Darwiche and Pierre Marquis. 2002. A knowledge compilation map.Google Scholar
- Journal of Arti cial Intelligence Research 17 ( 2002 ), 229-264. D. Deutsch. 1989. Quantum Computational Networks. Proceedings of the RoyalGoogle Scholar
- Society of London. Series A, Mathematical and Physical Sciences 425, 1868 ( 1989 ),Google Scholar
- 73-90. http://www.jstor.org/stable/2398494 David Deutsch and Richard Jozsa. 1992. Rapid Solution of Problems by QuantumGoogle Scholar
- Computation. Proceedings of the Royal Society of London Series A 439, 1907 (Dec.Google Scholar
- 1992 ), 553-558. https://doi.org/10.1098/rspa. 1992. 0167 Edward Farhi, Je rey Goldstone, and Sam Gutmann. 2014. A Quantum Approxi-Google Scholar
- mate Optimization Algorithm. arXiv e-prints, Article arXiv:1411.4028 (Nov 2014 ),Google Scholar
- arXiv:1411.4028 pages. arXiv:1411.4028 [quant-ph] Edward Farhi and Aram W Harrow. 2016. Quantum Supremacy through theGoogle Scholar
- Quantum Approximate Optimization Algorithm. arXiv:1602.07674 [quant-ph] Richard Phillips Feynman. 2006. QED: The strange theory of light and matter.Google Scholar
- Princeton University Press. E. Schuyler Fried, Nicolas P. D. Sawaya, Yudong Cao, Ian D. Kivlichan, JhonathanGoogle Scholar
- Romero, Alán Aspuru-Guzik, and Itay Hen, ed. 2018. qTorch: The quantum tensorGoogle Scholar
- contraction handler. PLoS ONE 13, 12 (12 2018 ). https://doi.org/10.1371/journal. Google ScholarCross Ref
- pone. 0208510 Lov K. Grover. 1996. A Fast Quantum Mechanical Algorithm for DatabaseGoogle Scholar
- Computing (Philadelphia, Pennsylvania, USA) ( STOC '96). ACM, New York, NY,Google Scholar
- USA, 212-219. https://doi.org/10.1145/237814.237866 Lov K. Grover. 2001. From Schrödinger's equation to the quantum search algo-Google ScholarDigital Library
- rithm. American Journal of Physics 69, 7 ( 2001 ), 769-777. https://doi.org/10.1119/Google ScholarCross Ref
- 1.1359518 arXiv:https://doi.org/10.1119/1.1359518 Aram W. Harrow and Ashley Montanaro. 2017. Quantum computationalGoogle Scholar
- supremacy. Nature 549 ( 13 09 2017 ), 203 EP-. https://doi.org/10.1038/nature23458 Joe Henson, Raymond Lal, and Matthew F Pusey. 2014. Theory-independentGoogle Scholar
- 16, 11 (nov 2014 ), 113043. https://doi.org/10.1088/ 1367-2630/16/11/113043 Steven Holtzen, Todd Millstein, and Guy Van den Broeck. 2019. GeneratingGoogle Scholar
- and Sampling Orbits for Lifted Probabilistic Inference. In Proceedings of the 35thGoogle Scholar
- Conference on Uncertainty in Arti cial Intelligence (UAI). Steven Holtzen, Guy Van den Broeck, and Todd Millstein. 2020. Scaling Exact In-Google Scholar
- ( 2020 ). https://doi.org/10.1145/342820 Hsin-Yuan Huang, Kishor Bharti, and Patrick Rebentrost. 2019. Near-term quan-Google Scholar
- tum algorithms for linear systems of equations. arXiv: 1909.07344 [quant-ph ] Yipeng Huang and Margaret Martonosi. 2019. QDB: From Quantum AlgorithmsGoogle Scholar
- Towards Correct Quantum Programs. In 9th Workshop on Evaluation and UsabilityGoogle Scholar
- of Programming Languages and Tools (PLATEAU 2018 ) (OpenAccess Series inGoogle Scholar
- Informatics (OASIcs), Vol. 67 ), Titus Barik, Joshua Sunshine, and Sarah ChasinsGoogle Scholar
- 4 : 1-4 : 14. https://doi.org/10.4230/OASIcs.PLATEAU. 2018. 4 Yipeng Huang and Margaret Martonosi. 2019. Statistical Assertions for ValidatingGoogle Scholar
- Patterns and Finding Bugs in Quantum Programs. In Proceedings of the 46thGoogle Scholar
- International Symposium on Computer Architecture (Phoenix, AZ) (ISCA '19). Phillip Kaye, Raymond La amme, and Michele Mosca. 2007. An Introduction toGoogle Scholar
Index Terms
- Logical abstractions for noisy variational Quantum algorithm simulation
Recommendations
Universal quantum circuit for N-qubit quantum gate: a programmable quantum gate
Quantum computation has attracted much attention, among other things, due to its potentialities to solve classical NP problems in polynomial time. For this reason, there has been a growing interest to build a quantum computer. One of the basic steps is ...
Graph-based simulation of quantum computation in the density matrix representation
Quantum-mechanical phenomena are playing an increasing role in information processing, as transistor sizes approach the nanometer level, and quantum circuits and data encoding methods appear in the securest forms of communication. Simulating such ...
Using HDLs for describing quantum circuits: a framework for efficient quantum algorithm simulation
CF '04: Proceedings of the 1st conference on Computing frontiersThe quantum algorithms could efficiently solve problems having exponential classical solutions [8]. The circuit model is considered as the most feasible implementation of the quantum algorithms [17]. This paper tries to find common ground between ...
Comments