Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1503.07525 · Physical Review Letters

Estimating Outcome Probabilities of Quantum Circuits Using Quasiprobabilities

Hakop Pashayan, Joel J. Wallman, Stephen D. Bartlett

Published Aug 10, 2015• 214 citations
arXivHTMLPDF

Abstract

We present a method for estimating the probabilities of outcomes of a quantum circuit using Monte Carlo sampling techniques applied to a quasiprobability representation. Our estimate converges to the true quantum probability at a rate determined by the total negativity in the circuit, using a measure of negativity based on the 1-norm of the quasiprobability. If the negativity grows at most polynomially in the size of the circuit, our estimator converges efficiently. These results highlight the role of negativity as a measure of nonclassical resources in quantum computation.

DOI
10.1103/physrevlett.115.070501

Related papers

Approximating outcome probabilities of linear optical circuits

Youngrong Lim, Changhun Oh

Abstract Quasiprobability representations are important tools for analyzing a quantum system, such as a quantum state or a quantum circuit. In this work, we propose classical algorithms specialized for approximating outcome probabilities of a linear optical circuit using quasiprobability distributions. Notably, we can reduce the negativity bound of a circuit from exponential to at most polynomial for specific cases by modulating the shapes of quasiprobability distributions thanks to the symmetry of the linear optical transformation in the phase space. Consequently, our scheme provides an efficient estimation of outcome probabilities within an additive-error whose precision depends on the classicality of the input state. When the classicality is high enough, we reach a polynomial-time estimation algorithm of a probability within a multiplicative-error by an efficient sampling from a log-concave function. By choosing appropriate input states and measurements, our results provide plenty of quantum-inspired classical algorithms for approximating various matrix functions beating best-known results. Moreover, we give sufficient conditions for the classical simulability of Gaussian Boson sampling using our approximating algorithm for any (marginal) outcome probability under the poly-sparse condition.

arXiv:2211.07184•npj Quantum Information•Dec 16, 2023•4 citations

Minimizing the negativity of quantum circuits in overcomplete quasiprobability representations

Denis A. Kulikov, V. I. Yashin, Aleksey K. Fedorov +1 more

The problem of simulatability of quantum processes using classical resources plays a cornerstone role for quantum computing. Quantum circuits can be simulated classically, e.g., using Monte Carlo sampling techniques applied to quasiprobability representations of circuits' basic elements, i.e., states, gates, and measurements. The effectiveness of the simulation is determined by the amount of the negativity in the representation of these basic elements. Here we develop an approach for minimizing the total negativity of a given quantum circuit with respect to quasiprobability representations, that are overcomplete, i.e., are such that the dimensionality of corresponding quasistochastic vectors and matrices is larger than the squared dimension of quantum states. Our approach includes both optimization over equivalent quasistochastic vectors and matrices, which appear due to the overcompleteness, and optimization over overcomplete frames. We demonstrate the performance of the developed approach on some illustrative cases, and show its significant advantage compared to the standard overcomplete quasistochastic representations. We also study the negativity minimization of noisy brick-wall random circuits via a combination of increasing frame dimension and applying gate merging technique. We demonstrate that the former approach appears to be more efficient in the case of a strong decoherence.

arXiv:2306.10758•Physical Review A•Jan 24, 2024•4 citations

Approximating outcome probabilities of linear optical circuits

Youngrong Lim, Changhun Oh

Abstract Quasiprobability representation is an important tool for analyzing a quantum system, such as a quantum state or a quantum circuit. In this work, we propose classical algorithms specialized for approximating outcome probabilities of a linear optical circuit using $s$-parameterized quasiprobability distributions. Notably, we can reduce the negativity bound of a circuit from exponential to at most polynomial for specific cases by modulating the shapes of quasiprobability distributions thanks to the symmetry of the linear optical transformation in the phase space. Consequently, our scheme renders an efficient estimation of outcome probabilities within an additive error whose precision depends on the classicality of the circuit. When the classicality is high enough, we reach a polynomial-time estimation algorithm of a probability within a multiplicative error by an efficient sampling from the log-concave function. By choosing appropriate input states and measurements, our results provide plenty of quantum-inspired classical algorithms for approximating various matrix functions beating best-known results. Moreover, we give sufficient conditions for the classical simulability of Gaussian boson sampling using the approximating algorithm for any (marginal) outcome probability under the poly-sparse condition.

•Mar 29, 2023•1 citation

Faster Born probability estimation via gate merging and frame optimisation

Nikolaos Koukoulekidis, Hyukjoon Kwon, Hyejung H. Jee +2 more

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.

Quantum•Oct 13, 2022•6 citations

Faster Born probability estimation via gate merging and frame optimisation

Nikolaos Koukoulekidis, Hyukjoon Kwon, Hyejung H. Jee +2 more

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:2202.12114•Feb 24, 2022•0 citations

Discrete-variable simulation and classical probability estimation of bosonic quantum computing

Alex Maltesson

This thesis investigates two complementary computational approaches to obtaining the outcome statistics of bosonic quantum experiments without directly performing the experiments themselves. In particular, we consider how continuous-variable quantum computations can be approximated using discrete-variable quantum systems and how bosonic outcome probabilities can be estimated using classical computational methods.The first part of the thesis focuses on the relation between continuous-variable (CV) and discrete-variable (DV) quantum computation. A framework is presented for approximating realistic CV quantum computations, consisting of polynomially bounded-energy states and a polynomial number of elementary gates, using DV quantum hardware. The proposed approximation error scales polynomially with the number of modes and can be made arbitrarily small by increasing the dimension of the simulating qudits. However, some technical aspects of the derivation remain to be rigorously justified. If these can be resolved, the result would establish a computational equivalence between the two paradigms. The remaining potential issues and possible approaches to resolving them are discussed.In the second part, we develop a framework for classically estimating individual outcome probabilities of general bosonic experiments using Monte Carlo methods based on (s)-ordered phase-space quasi-probability distributions. The resulting sampling complexity depends on properties of the phase-space quasi-probability distributions, in particular, their negativity and range, showing that negativity alone does not prevent efficient classical estimation. The outcome probability can be decomposed in several ways, giving rise to distinct trade-offs between these quantities. We discuss how experimentally relevant error channels can be incorporated into the framework and how they affect the classical estimation complexity, using pure loss as an illustrative example.Together, these results contribute to understanding the resources required to reproduce the outcome statistics of bosonic quantum experiments using both DV quantum and classical computation.

•Jan 1, 2026•0 citations
We present a method for estimating the probabilities of outcomes of a quantum circuit using Monte Carlo sampling techniques applied to a quasiprobability representation. Our estimate converges to the true quantum probability at a rate determined by the total negativity in the circuit, using a measure of negativity based on the 1-norm of the quasiprobability. If the negativity grows at most polynomially in the size of the circuit, our estimator converges efficiently. These results highlight the role of negativity as a measure of nonclassical resources in quantum computation.
Abstract Quasiprobability representations are important tools for analyzing a quantum system, such as a quantum state or a quantum circuit. In this work, we propose classical algorithms specialized for approximating outcome probabilities of a linear optical circuit using quasiprobability distributions. Notably, we can reduce the negativity bound of a circuit from exponential to at most polynomial for specific cases by modulating the shapes of quasiprobability distributions thanks to the symmetry of the linear optical transformation in the phase space. Consequently, our scheme provides an efficient estimation of outcome probabilities within an additive-error whose precision depends on the classicality of the input state. When the classicality is high enough, we reach a polynomial-time estimation algorithm of a probability within a multiplicative-error by an efficient sampling from a log-concave function. By choosing appropriate input states and measurements, our results provide plenty of quantum-inspired classical algorithms for approximating various matrix functions beating best-known results. Moreover, we give sufficient conditions for the classical simulability of Gaussian Boson sampling using our approximating algorithm for any (marginal) outcome probability under the poly-sparse condition.
The problem of simulatability of quantum processes using classical resources plays a cornerstone role for quantum computing. Quantum circuits can be simulated classically, e.g., using Monte Carlo sampling techniques applied to quasiprobability representations of circuits' basic elements, i.e., states, gates, and measurements. The effectiveness of the simulation is determined by the amount of the negativity in the representation of these basic elements. Here we develop an approach for minimizing the total negativity of a given quantum circuit with respect to quasiprobability representations, that are overcomplete, i.e., are such that the dimensionality of corresponding quasistochastic vectors and matrices is larger than the squared dimension of quantum states. Our approach includes both optimization over equivalent quasistochastic vectors and matrices, which appear due to the overcompleteness, and optimization over overcomplete frames. We demonstrate the performance of the developed approach on some illustrative cases, and show its significant advantage compared to the standard overcomplete quasistochastic representations. We also study the negativity minimization of noisy brick-wall random circuits via a combination of increasing frame dimension and applying gate merging technique. We demonstrate that the former approach appears to be more efficient in the case of a strong decoherence.
Abstract Quasiprobability representation is an important tool for analyzing a quantum system, such as a quantum state or a quantum circuit. In this work, we propose classical algorithms specialized for approximating outcome probabilities of a linear optical circuit using sss-parameterized quasiprobability distributions. Notably, we can reduce the negativity bound of a circuit from exponential to at most polynomial for specific cases by modulating the shapes of quasiprobability distributions thanks to the symmetry of the linear optical transformation in the phase space. Consequently, our scheme renders an efficient estimation of outcome probabilities within an additive error whose precision depends on the classicality of the circuit. When the classicality is high enough, we reach a polynomial-time estimation algorithm of a probability within a multiplicative error by an efficient sampling from the log-concave function. By choosing appropriate input states and measurements, our results provide plenty of quantum-inspired classical algorithms for approximating various matrix functions beating best-known results. Moreover, we give sufficient conditions for the classical simulability of Gaussian boson sampling using the approximating algorithm for any (marginal) outcome probability under the poly-sparse condition.
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.
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+TTT 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.
This thesis investigates two complementary computational approaches to obtaining the outcome statistics of bosonic quantum experiments without directly performing the experiments themselves. In particular, we consider how continuous-variable quantum computations can be approximated using discrete-variable quantum systems and how bosonic outcome probabilities can be estimated using classical computational methods.The first part of the thesis focuses on the relation between continuous-variable (CV) and discrete-variable (DV) quantum computation. A framework is presented for approximating realistic CV quantum computations, consisting of polynomially bounded-energy states and a polynomial number of elementary gates, using DV quantum hardware. The proposed approximation error scales polynomially with the number of modes and can be made arbitrarily small by increasing the dimension of the simulating qudits. However, some technical aspects of the derivation remain to be rigorously justified. If these can be resolved, the result would establish a computational equivalence between the two paradigms. The remaining potential issues and possible approaches to resolving them are discussed.In the second part, we develop a framework for classically estimating individual outcome probabilities of general bosonic experiments using Monte Carlo methods based on (s)-ordered phase-space quasi-probability distributions. The resulting sampling complexity depends on properties of the phase-space quasi-probability distributions, in particular, their negativity and range, showing that negativity alone does not prevent efficient classical estimation. The outcome probability can be decomposed in several ways, giving rise to distinct trade-offs between these quantities. We discuss how experimentally relevant error channels can be incorporated into the framework and how they affect the classical estimation complexity, using pure loss as an illustrative example.Together, these results contribute to understanding the resources required to reproduce the outcome statistics of bosonic quantum experiments using both DV quantum and classical computation.