Just Like the Real Thing: Fast Weak Simulation of Quantum Computation
Authors:
- 1 July 2020
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1-6
Abstract
Quantum computers promise significant speedups in solving problems intractable for conventional computers but, despite recent progress, remain limited in scaling and availability. Therefore, quantum software and hardware development heavily rely on simulation that runs on conventional computers. Most such approaches perform strong simulation in that they explicitly compute amplitudes of quantum states. However, such information is not directly observable from a physical quantum computer because quantum measurements produce random samples from probability distributions defined by those amplitudes. In this work, we focus on weak simulation that aims to produce outputs which are statistically indistinguishable from those of error-free quantum computers. We develop algorithms for weak simulation based on quantum state representation in terms of decision diagrams. We compare them to using state-vector arrays and binary search on prefix sums to perform sampling. Empirical validation shows, for the first time, that this enables mimicking of physical quantum computers of significant scale.Keywords
All Related Versions
This publication has 20 references indexed in Scilit:
- One-pass Design of Reversible Circuits: Combining Embedding and Synthesis for Reversible LogicIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2017
- Simulations of Shor’s algorithm using matrix product statesQuantum Information Processing, 2017
- QX: A high-performance quantum computer simulation platform2017
- Quantum algorithms: an overviewnpj Quantum Information, 2016
- QMDDs: Efficient Quantum Function Representation and ManipulationIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2015
- Quantum Circuit Simulation2009
- An XQDD-Based Verification Method for Quantum CircuitsIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 2008
- Improved BDD Algorithms for the Simulation of Quantum Circuits2008
- Analysis and Synthesis of Quantum Circuits by Using Quantum Decision Diagrams2006
- Algorithms for quantum computation: discrete logarithms and factoring2002