Faster Born probability estimation via gate merging and frame optimisation

Abstract

Outcome probability estimation via classical methods is an important task for validating quantum computing devices. Outcome probabilities of any quantum circuit can be estimated using Monte Carlo sampling, where the amount of negativity present in the circuit frame representation quantifies the overhead on the number of samples required to achieve a certain precision. In this paper, we propose two classical sub-routines: circuit gate merging and frame optimisation, which optimise the circuit representation to reduce the sampling overhead. We show that the runtimes of both sub-routines scale polynomially in circuit size and gate depth. Our methods are applicable to general circuits, regardless of generating gate sets, qudit dimensions and the chosen frame representations for the circuit components. We numerically demonstrate that our methods provide improved scaling in the negativity overhead for all tested cases of random circuits with Clifford+$T$ and Haar-random gates, and that the performance of our methods compares favourably with prior quasi-probability simulators as the number of non-Clifford gates increases.

arXiv comment15 pages, 5 figures. Comments welcome

References in corpus (56)

• Quantum Computing in the NISQ era and beyond
• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Variational Quantum Algorithms
• Global Optimization by Basin-Hopping and the Lowest Energy Structures of Lennard-Jones Clusters Containing up to 110 Atoms
• Probing many-body dynamics on a 51-atom quantum simulator
• Quantum computational advantage using photons
• Improved Simulation of Stabilizer Circuits
• Error mitigation for short-depth quantum circuits
• Characterizing Quantum Supremacy in Near-Term Devices
• Extending the computational reach of a noisy superconducting quantum processor
• Quantum Computational Supremacy
• Practical Quantum Error Mitigation for Near-Future Applications
• A blueprint for demonstrating quantum supremacy with superconducting qubits
• Positive Wigner functions render classical simulation of quantum computation efficient
• Efficient Classical Simulation of Continuous Variable Quantum Information Processes
• Application of a resource theory for magic states to fault-tolerant quantum computing
• Negative Quasi-Probability as a Resource for Quantum Computation
• Mitigating measurement errors in multi-qubit experiments
• Hudson's Theorem for finite-dimensional quantum systems
• Classical simulation of noninteracting-fermion quantum circuits
• Improved classical simulation of quantum circuits dominated by Clifford gates
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• Trading classical and quantum computational resources
• Average-case complexity versus approximate simulation of commuting quantum computations
• Simulation of quantum circuits by low-rank stabilizer decompositions
• Most quantum states are too entangled to be useful as computational resources
• The XZZX Surface Code
• Estimating outcome probabilities of quantum circuits using quasiprobabilities
• Novel constructions for the fault-tolerant Toffoli gate
• Sufficient Conditions for Efficient Classical Simulation of Quantum Optics
• Quantifying quantum speedups: improved classical simulation from tighter magic monotones
• Quantifying magic for multi-qubit operations
• Contextuality and Wigner function negativity in qubit quantum computation
• Frame representations of quantum mechanics and the necessity of negativity in quasi-probability representations
• Robustness of Magic and Symmetries of the Stabiliser Polytope
• On the hardness of classically simulating the one clean qubit model
• Architectures for quantum simulation showing a quantum speedup
• Quantum Supremacy for Simulating A Translation-Invariant Ising Spin Model
• Framed Hilbert space: hanging the quasi-probability pictures of quantum theory
• Simulation of Qubit Quantum Circuits via Pauli Propagation
• Impossibility of Classically Simulating One-Clean-Qubit Computation
• Efficient classical simulation of matchgate circuits with generalized inputs and measurements
• Quantum interference as a resource for quantum speedup
• Quasiprobability distribution functions for periodic phase-spaces: I. Theoretical Aspects
• Unbiased Simulation of Near-Clifford Quantum Circuits
• From estimation of quantum probabilities to simulation of quantum circuits
• Improved upper bounds on the stabilizer rank of magic states
• Quantum advantage of unitary Clifford circuits with magic state inputs
• Fast estimation of outcome probabilities for quantum circuits
• Extended Cahill and Glauber formalism for finite dimensional spaces II. Applications in quantum tomography and quantum teleportation
• Further extensions of Clifford circuits and their classical simulation complexities
• Computational power of matchgates with supplementary resources
• Approximate stabilizer rank and improved weak simulation of Clifford-dominated circuits for qudits
• Clifford recompilation for faster classical simulation of quantum circuits
• Improved Simulation of Quantum Circuits by Fewer Gaussian Eliminations
• Efficient classical simulation and benchmarking of quantum processes in the Weyl basis

Cited by in corpus (5)

• Quantifying nonstabilizerness of matrix product states
• Measuring nonstabilizerness via multifractal flatness
• Extending Classically Simulatable Bounds of Clifford Circuits with Nonstabilizer States via Framed Wigner Functions
• Minimizing the negativity of quantum circuits in overcomplete quasiprobability representations
• Ideal stochastic process modeling with post-quantum quasiprobabilistic theories