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:1604.07517 · Advanced Quantum Technologies

Quantifiable Simulation of Quantum Computation beyond Stochastic Ensemble Computation

Jeongho Bang, Junghee Ryu, Chang‐Woo Lee, Ki Hyuk Yee, Jinhyoung Lee, Wonmin Son

Published Aug 24, 2018• 4 citations
arXivHTMLPDF

Abstract

Abstract In this study, a distinctive feature of quantum computation (QC) is characterized. To this end, a seemingly‐powerful classical computing model, called “stochastic ensemble machine (SEnM),” is considered. The SEnM runs with an ensemble consisting of finite copies of a single probabilistic machine, hence is as powerful as a probabilistic Turing machine (PTM). Then the hypothesis—that is, the SEnM can effectively simulate a general circuit model of QC—is tested by introducing an information‐theoretic inequality, named readout inequality. The inequality is satisfied by the SEnM and imposes a critical condition: if the hypothesis holds, the inequality should be satisfied by the probing model of QC. However, it is shown that the above hypothesis is not generally accepted with the inequality violation; namely, such a simulation necessarily fails, implying that PTM ⊆ QC.

DOI
10.1002/qute.201800037

Related papers

Quantifiable Simulation of Quantum Computation beyond Stochastic Ensemble Computation (Adv. Quantum Technol. 2/2018)

Jeongho Bang, Junghee Ryu, Chang‐Woo Lee +3 more

A model of quantum computation (QC) is compared with a generalized classical computation model, named stochastic ensemble computation (SEnC), in article number 1800037 by Jeongho Bang, Jinhyoung Lee, Wonmin Son and co-workers. SEnC runs in an ensemble consisting of finite copies of single probabilistic entities, and hence is a generalized probabilistic Turing machine. Impossibility of simulating a QC in the SEnC is proved, manifesting “QC is characterized beyond any classical probabilistic computation,” i.e., SEnC ⊆ QC.

Advanced Quantum Technologies•Oct 1, 2018•0 citations

Reflections on probabilistic compared to quantum computational devices

Giuseppe Corrente

In this article, we underline and compare different quantum and deterministic models of computation by means of a probabilistic point of view. The main models used for this are deterministic, probabilistic and quantum Turing machines (DTM, PTM and QTM, respectively). Then we suggest that extending PTM with only part of quantum features is not useful to implement real quantum supremacy if we don’t incorporate them fully. This is done reviewing some notorious quantum physical experiments and quantum algorithms, showing that generally PTM does not fit for them, also if in some particular cases it fits.Here we compare probabilistic and quantum models of computation to underline some common features and differences.

International Journal of Parallel Emergent and Distributed Systems•Aug 11, 2020•2 citations

The Classical Boundary of Quantum Computation: History-Resolved Causal Stochastic Machines and the Cost of Classicalization

Kyoungho Cho, Junghee Ryu, Minsu Kim +1 more

What separates quantum computation from classical computation when a classical model may retain every branch history and arbitrary causal memory? We study this question using history-resolved causal stochastic machines (HCSMs), which describe positive causal history laws. Probabilistic Turing machines (PTMs) embed in stochastic-ensemble models (SEnMs), which in turn embed in HCSMs. We prove that HCSM history laws coincide exactly with the fixed-basis, prefix-preserving diagonal sector of ideal quantum processes, denoted by $\mathsf{PTM}_{\rm proc}$ and distinguished here from algorithmic quantum Turing machines (QTMs). Coherent quantum processes extend strictly beyond this sector. The boundary is already visible in reversibility. Born-probability shadows of unitary gates preserve inverse composition exactly for basis permutations with phases. Outside this class, an exact positive stochastic simulation that supports universal quantum continuations must retain predictive information absent from visible probabilities. An inverse-recovery identity quantifies this phase ledger, and universal continuation forces the retained probability law to be tomographically sufficient for the quantum state. Under continuous full-state encoding assumptions, this requirement yields quantum-state dimension lower bounds. The familiar slogan $\mathsf{PTM}\subseteq\mathsf{QTM}$ is thereby sharpened into a precise classical boundary and a no-free-classicalization principle. Complete classical branching does not remove the predictive information needed to represent quantum coherence.

quant-pharXiv:2610.22750•Oct 19, 2026•0 citations

Quantum computing and quantum complexity theory

Umesh V. Vazirani

There is strong evidence that computers based upon the principles of quantum physics represent an inherently new and more powerful model of computation. Such computers violate the modern form of the Church-Turing thesis (which lies at the foundations of computer science). This thesis can be informally summarized as follows: all physical implementations of computing devices can be described by the same abstract model of computation-the probabilistic Turing Machine or the equivalent random access machine. In this paper, we will describe two formal models for quantum computers: quantum circuits and quantum Turing Machines, introduced by Deutsch [1985].

IEEE International Symposium on Circuits and Systems proceedings•Jan 1, 2000•0 citations

On the Power of Quantum Computation

Daniel R. Simon

The quantum model of computation is a model, analogous to the probabilistic Turing machine (PTM), in which the normal laws of chance are replaced by those obeyed by particles on a quantum mechanical scale, rather than the rules familiar to us from the macroscopic world. We present here a problem of distinguishing between two fairly natural classes of functions, which can provably be solved exponentially faster in the quantum model than in the classical probabilistic one, when the function is given as an oracle drawn equiprobably from the uniform distribution on either class. We thus offer compelling evidence that the quantum model may have significantly more complexity theoretic power than the PTM. In fact, drawing on this work, Shor has recently developed remarkable new quantum polynomial-time algorithms for the discrete logarithm and integer factoring problems.

SIAM Journal on Computing•Oct 1, 1997•1,368 citations

Approximate simulation of circuits with probabilistic behavior

Alexandru Paler, Josef Kinseher, Ilia Polian +1 more

Various emerging technologies promise advantages with respect to integration density, performance or power consumption, at the cost of approximate or probabilistic behavior. Approximate computing, where limited computational inaccuracies are tolerated at the system or application level is therefore of increasing interest. This paper investigates the use of stochastic computing (SC) as a tool for approximate simulation of probabilistic behavior. SC has the advantage of processing probabilities directly at very low hardware cost. It also allows accuracy to be traded for run-time in a natural way (progressive precision). AS a target technology to be simulated, we choose quantum computing circuits, whose behavior is inherently probabilistic and cannot be efficiently simulated by conventional (classical) means. We show how complex operations such as superposition and entanglement can be handled by SC. Finally, we report experimental results on software-based simulation of representative quantum circuits, both stand-alone and FPGA-supported. The results show that the SC implementations are orders of magnitude more compact than those based on classical circuits. Accurate results may require very long simulation runs, but run-times can be reduced by exploiting SC's progressive precision property.

Proceedings•Oct 1, 2013•11 citations
Abstract In this study, a distinctive feature of quantum computation (QC) is characterized. To this end, a seemingly‐powerful classical computing model, called “stochastic ensemble machine (SEnM),” is considered. The SEnM runs with an ensemble consisting of finite copies of a single probabilistic machine, hence is as powerful as a probabilistic Turing machine (PTM). Then the hypothesis—that is, the SEnM can effectively simulate a general circuit model of QC—is tested by introducing an information‐theoretic inequality, named readout inequality. The inequality is satisfied by the SEnM and imposes a critical condition: if the hypothesis holds, the inequality should be satisfied by the probing model of QC. However, it is shown that the above hypothesis is not generally accepted with the inequality violation; namely, such a simulation necessarily fails, implying that PTM ⊆ QC.
A model of quantum computation (QC) is compared with a generalized classical computation model, named stochastic ensemble computation (SEnC), in article number 1800037 by Jeongho Bang, Jinhyoung Lee, Wonmin Son and co-workers. SEnC runs in an ensemble consisting of finite copies of single probabilistic entities, and hence is a generalized probabilistic Turing machine. Impossibility of simulating a QC in the SEnC is proved, manifesting “QC is characterized beyond any classical probabilistic computation,” i.e., SEnC ⊆ QC.
In this article, we underline and compare different quantum and deterministic models of computation by means of a probabilistic point of view. The main models used for this are deterministic, probabilistic and quantum Turing machines (DTM, PTM and QTM, respectively). Then we suggest that extending PTM with only part of quantum features is not useful to implement real quantum supremacy if we don’t incorporate them fully. This is done reviewing some notorious quantum physical experiments and quantum algorithms, showing that generally PTM does not fit for them, also if in some particular cases it fits.Here we compare probabilistic and quantum models of computation to underline some common features and differences.
What separates quantum computation from classical computation when a classical model may retain every branch history and arbitrary causal memory? We study this question using history-resolved causal stochastic machines (HCSMs), which describe positive causal history laws. Probabilistic Turing machines (PTMs) embed in stochastic-ensemble models (SEnMs), which in turn embed in HCSMs. We prove that HCSM history laws coincide exactly with the fixed-basis, prefix-preserving diagonal sector of ideal quantum processes, denoted by PTMproc\mathsf{PTM}_{\rm proc}PTMproc​ and distinguished here from algorithmic quantum Turing machines (QTMs). Coherent quantum processes extend strictly beyond this sector. The boundary is already visible in reversibility. Born-probability shadows of unitary gates preserve inverse composition exactly for basis permutations with phases. Outside this class, an exact positive stochastic simulation that supports universal quantum continuations must retain predictive information absent from visible probabilities. An inverse-recovery identity quantifies this phase ledger, and universal continuation forces the retained probability law to be tomographically sufficient for the quantum state. Under continuous full-state encoding assumptions, this requirement yields quantum-state dimension lower bounds. The familiar slogan PTM⊆QTM\mathsf{PTM}\subseteq\mathsf{QTM}PTM⊆QTM is thereby sharpened into a precise classical boundary and a no-free-classicalization principle. Complete classical branching does not remove the predictive information needed to represent quantum coherence.
There is strong evidence that computers based upon the principles of quantum physics represent an inherently new and more powerful model of computation. Such computers violate the modern form of the Church-Turing thesis (which lies at the foundations of computer science). This thesis can be informally summarized as follows: all physical implementations of computing devices can be described by the same abstract model of computation-the probabilistic Turing Machine or the equivalent random access machine. In this paper, we will describe two formal models for quantum computers: quantum circuits and quantum Turing Machines, introduced by Deutsch [1985].
The quantum model of computation is a model, analogous to the probabilistic Turing machine (PTM), in which the normal laws of chance are replaced by those obeyed by particles on a quantum mechanical scale, rather than the rules familiar to us from the macroscopic world. We present here a problem of distinguishing between two fairly natural classes of functions, which can provably be solved exponentially faster in the quantum model than in the classical probabilistic one, when the function is given as an oracle drawn equiprobably from the uniform distribution on either class. We thus offer compelling evidence that the quantum model may have significantly more complexity theoretic power than the PTM. In fact, drawing on this work, Shor has recently developed remarkable new quantum polynomial-time algorithms for the discrete logarithm and integer factoring problems.
Various emerging technologies promise advantages with respect to integration density, performance or power consumption, at the cost of approximate or probabilistic behavior. Approximate computing, where limited computational inaccuracies are tolerated at the system or application level is therefore of increasing interest. This paper investigates the use of stochastic computing (SC) as a tool for approximate simulation of probabilistic behavior. SC has the advantage of processing probabilities directly at very low hardware cost. It also allows accuracy to be traded for run-time in a natural way (progressive precision). AS a target technology to be simulated, we choose quantum computing circuits, whose behavior is inherently probabilistic and cannot be efficiently simulated by conventional (classical) means. We show how complex operations such as superposition and entanglement can be handled by SC. Finally, we report experimental results on software-based simulation of representative quantum circuits, both stand-alone and FPGA-supported. The results show that the SC implementations are orders of magnitude more compact than those based on classical circuits. Accurate results may require very long simulation runs, but run-times can be reduced by exploiting SC's progressive precision property.