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:2610.22750

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

Kyoungho Cho, Junghee Ryu, Minsu Kim, Jeongho Bang

quant-phSubmitted Oct 15, 2026• Announced Oct 19, 2026• 0 citations
arXivHTMLPDF

Abstract

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.

AI Summary

The paper asks what information a positive classical stochastic model must retain to reproduce coherent quantum composition, rather than merely final output statistics. It defines history-resolved causal stochastic machines (HCSMs), whose transition kernels may depend on the complete past, for finite horizons and finite or countable configuration spaces. Using probability-chain-rule factorization and explicit Kraus maps, it identifies HCSM history laws with fixed-basis, prefix-preserving quantum processes whose channels satisfy $\Phi=D_{\rm out}\Phi D_{\rm in}$. For a unitary’s Born shadow, $B(U)_{yx}=|U_{yx}|^2$, it shows that $B(U^\dagger)B(U)=I$ holds exactly for monomial unitaries: permutations with phases. Beyond this visible-probability description, exact inverse recovery from a retained record $(Y,Z)$ requires $I(X;Z\mid Y)=H(X\mid Y)$; approximate recovery gives a Fano-type bound. Supporting tomographically complete future continuations requires distinct reachable density matrices to have operationally distinct retained laws. Continuous full-state encodings therefore need parameter dimension at least $2^{n+1}-2$ for pure $n$-qubit states, or $4^n-1$ for mixed states. Finite-precision simulations use continuation-distance incompatibility graphs to bound deterministic predictive codebooks; for finite binary-query banks, the optimum equals the graph’s chromatic number. Numerical examples compare restricted and universal continuation requirements. The stated scope excludes complexity-class separation or impossibility of positive classical simulation with sufficient memory. The dimension bounds require continuity and full-manifold coverage, concern probability-law parameters rather than sampled-state memory, and do not follow from a countable gate orbit. Codebook index bounds assume deterministic encodings; arbitrary real kernels receive ideal-process, not necessarily effective finite-gate, realizations.

Likely largely AI-generatedOverclaimsIncrementalUnclear noveltyStrong assumptions

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Comments
28 pages (including Appendix), 5 figures

Related papers

Relationships between quantum and classical space-bounded complexity classes

John Watrous

This paper investigates the relative power of space-bounded quantum and classical (probabilistic) computational models. The following relationships are proved. 1. Any probabilistic Turing machine (PTM) which runs in space s and which halts absolutely (i.e. halts with certainty after a finite number of steps) can be simulated in space O(s) by a quantum Turing machine (QTM). If the PTM operates with bounded error, then the QTM may be taken to operate with bounded error as well, although the QTM may not halt absolutely in this case. In the unbounded error case, the QTM may be taken to halt absolutely. 2. Any QTM running in space s can be simulated by an unbounded error PTM running in space O(s). No assumptions on the probability of error or Turing time for the QTM are required, but it is assumed that all transition amplitudes of the quantum machine are rational. It follows that unbounded error, space O(s) bounded quantum Turing machines and probabilistic Turing machines are equivalent in power. This implies that any space s QTM can be simulated deterministically in space O(s/sup 2/), and further that any (unbounded-error) QTM running in log-space can be simulated in NC/sup 2/ We also consider quantum analogues of nondeterministic and one-sided error probabilistic space-bounded classes, and prove some simple relationships regarding these classes.

IEEE Conference on Computational Complexity (CCC)•Nov 27, 2002•13 citations

Quantum Complexity Theory

Ethan Bernstein, Umesh V. Vazirani

In this paper we study quantum computation from a complexity theoretic viewpoint. Our first result is the existence of an efficient universal quantum Turing machine in Deutsch's model of a quantum Turing machine (QTM) [Proc. Roy. Soc. London Ser. A, 400 (1985), pp. 97--117]. This construction is substantially more complicated than the corresponding construction for classical Turing machines (TMs); in fact, even simple primitives such as looping, branching, and composition are not straightforward in the context of quantum Turing machines. We establish how these familiar primitives can be implemented and introduce some new, purely quantum mechanical primitives, such as changing the computational basis and carrying out an arbitrary unitary transformation of polynomially bounded dimension. We also consider the precision to which the transition amplitudes of a quantum Turing machine need to be specified. We prove that $O(\log T)$ bits of precision suffice to support a T step computation. This justifies the claim that the quantum Turing machine model should be regarded as a discrete model of computation and not an analog one. We give the first formal evidence that quantum Turing machines violate the modern (complexity theoretic) formulation of the Church--Turing thesis. We show the existence of a problem, relative to an oracle, that can be solved in polynomial time on a quantum Turing machine, but requires superpolynomial time on a bounded-error probabilistic Turing machine, and thus not in the class $\BPP$. The class $\BQP$ of languages that are efficiently decidable (with small error-probability) on a quantum Turing machine satisfies $\BPP \subseteq \BQP \subseteq \Ptime^{\SP}$. Therefore, there is no possibility of giving a mathematical proof that quantum Turing machines are more powerful than classical probabilistic Turing machines (in the unrelativized setting) unless there is a major breakthrough in complexity theory.

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

Quantum Source Completions and Memory Environment Tradeoffs

Jeremy Rodgers

How much internal quantum memory is needed to reproduce a stationary stochastic process, and how does reducing that memory change the environmental resources required when output records are retained? This paper establishes exact quantum-source constructions and resource bounds under explicitly specified readout and retained-output conditions. A general completion theorem identifies the minimum Hilbert-space dimension for stationary triple data in the orthogonal-current-symbol source class: it equals the sum of the complex positive-semidefinite ranks of the middle-symbol slices. An attaining construction reproduces the entire canonical stationary order-two process. For the delayed trine process, the minimum classical hidden Markov model requires nine states at every non-independent parameter value. Quantum instruments reproduce the same complete output law using four-dimensional memory throughout the parameter range, with four dimensions proved necessary in a certified low-noise regime and three dimensions both sufficient and necessary on an explicit high-noise interval. The paper then separates reusable memory dimension from environmental dilation cost. On the certified high-noise interval, the exact one-step Pareto frontier consists of a three-dimensional source with recorded-channel Choi rank nine and a four-dimensional source with rank three. Here, Choi rank measures the minimum initially pure environmental remainder dimension for the channel retaining both the emitted classical symbol and final quantum memory. A separate mixed-support qutrit construction at noise parameter 0.99 improves complete-history costs and gives upper bounds close to universal lower bounds. These results show why optimizing a single step need not optimize a retained multi-step history. The analysis also distinguishes complete channels, fixed-input states and archive-only outputs, and demonstrates how access to a retained reference can distinguish generators with identical passive output statistics. Full-word proofs, algebraic complete-positivity certificates, a technical companion and reproducibility materials accompany the results. The exact intermediate memory boundary and complete-history optimum remain open. All results use standard quantum probabilities and apply to the stated operational resource models; they do not establish total hardware, energy or thermodynamic minima.

•Oct 28, 2026•0 citations

Coherence Response in Noisy Quantum Measurements

Zachariah Malik, Quinn Langfitt, Zain Saleem

Readout error models for noisy quantum devices almost universally assume that measurement noise is classical: the measurement statistics are obtained from the ideal computational-basis populations by a column-stochastic assignment matrix $A$. This description is equivalent to assuming that the effective positive-operator-valued measurement (POVM) is diagonal in the measurement basis, and therefore completely insensitive to quantum coherences. We relax this assumption and derive a fully general expression for the observed measurement probabilities under arbitrary completely positive trace-preserving (CPTP) noise preceding a computational-basis measurement. Writing the ideal post-circuit state $\tildeρ$ in terms of its populations $x$ and coherences $y$, we show that the observed probability vector $z$ satisfies $z = A x + C y$, where $A$ is the familiar classical assignment matrix and $C$ is a coherence-response matrix constructed from the off-diagonal matrix elements of the effective POVM in the computational basis. The classical model $z = A x$ arises if and only if all POVM elements are diagonal; in this sense $C$ quantifies accessible information about coherent readout distortions and interference between computational-basis states, all of which are invisible to models that retain only $A$. Our numerical experiments show that incorporating $C$ into readout recovery can improve fidelity over classical inversion and enable selective Pauli twirling with exponentially reduced circuit overhead. This work therefore provides a natural, fully general framework for coherence-sensitive readout modeling on current and future quantum devices.

quant-pharXiv:2512.13949•Dec 17, 2025•2 citations

Quantifiable Simulation of Quantum Computation beyond Stochastic Ensemble Computation

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

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.

arXiv:1604.07517•Advanced Quantum Technologies•Aug 24, 2018•4 citations

Quantum complexity theory

Ethan Bernstein, Umesh V. Vazirani

Abstract. In this paper we study quantum computation from a complexity theoretic viewpoint. Our rst result is the existence of an ecient universal quantum Turing machine in Deutsch’s model of a quantum Turing machine (QTM) [Proc. Roy. Soc. London Ser. A, 400 (1985), pp. 97{117]. This construction is substantially more complicated than the corresponding construction for classical Turing machines (TMs); in fact, even simple primitives such as looping, branching, and composition are not straightforward in the context of quantum Turing machines. We establish how these familiar primitives can be implemented and introduce some new, purely quantum mechanical primitives, such as changing the computational basis and carrying out an arbitrary unitary transformation of polynomially bounded dimension. We also consider the precision to which the transition amplitudes of a quantum Turing machine need to be specied. We prove that O(log T) bits of precision suce to support a T step computation. This justies the claim that the quantum Turing machine model should be regarded as a discrete model of computation and not an analog one. We give the rst formal evidence that quantum Turing machines violate the modern (complexity theoretic) formulation of the Church{Turing thesis. We show the existence of a problem, relative to an oracle, that can be solved in polynomial time on a quantum Turing machine, but requires superpolynomial time on a bounded-error probabilistic Turing machine, and thus not in the class BPP. The class BQP of languages that are eciently decidable (with small error-probability) on a quantum Turing machine satises BPP ⊆ BQP ⊆ P]P. Therefore, there is no possibility of giving a mathematical proof that quantum Turing machines are more powerful than classical probabilistic Turing machines (in the unrelativized setting) unless there is a major breakthrough in complexity theory.

ACM Symposium on Theory of Computing (STOC)•Jan 1, 1993•1,413 citations
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.
The paper asks what information a positive classical stochastic model must retain to reproduce coherent quantum composition, rather than merely final output statistics. It defines history-resolved causal stochastic machines (HCSMs), whose transition kernels may depend on the complete past, for finite horizons and finite or countable configuration spaces.
Using probability-chain-rule factorization and explicit Kraus maps, it identifies HCSM history laws with fixed-basis, prefix-preserving quantum processes whose channels satisfy Φ=DoutΦDin\Phi=D_{\rm out}\Phi D_{\rm in}Φ=Dout​ΦDin​. For a unitary’s Born shadow, B(U)yx=∣Uyx∣2B(U)_{yx}=|U_{yx}|^2B(U)yx​=∣Uyx​∣2, it shows that B(U†)B(U)=IB(U^\dagger)B(U)=IB(U†)B(U)=I holds exactly for monomial unitaries: permutations with phases. Beyond this visible-probability description, exact inverse recovery from a retained record (Y,Z)(Y,Z)(Y,Z) requires I(X;Z∣Y)=H(X∣Y)I(X;Z\mid Y)=H(X\mid Y)I(X;Z∣Y)=H(X∣Y); approximate recovery gives a Fano-type bound. Supporting tomographically complete future continuations requires distinct reachable density matrices to have operationally distinct retained laws. Continuous full-state encodings therefore need parameter dimension at least 2n+1−22^{n+1}-22n+1−2 for pure nnn-qubit states, or 4n−14^n-14n−1 for mixed states.
Finite-precision simulations use continuation-distance incompatibility graphs to bound deterministic predictive codebooks; for finite binary-query banks, the optimum equals the graph’s chromatic number. Numerical examples compare restricted and universal continuation requirements.
The stated scope excludes complexity-class separation or impossibility of positive classical simulation with sufficient memory. The dimension bounds require continuity and full-manifold coverage, concern probability-law parameters rather than sampled-state memory, and do not follow from a countable gate orbit. Codebook index bounds assume deterministic encodings; arbitrary real kernels receive ideal-process, not necessarily effective finite-gate, realizations.
This paper investigates the relative power of space-bounded quantum and classical (probabilistic) computational models. The following relationships are proved. 1. Any probabilistic Turing machine (PTM) which runs in space s and which halts absolutely (i.e. halts with certainty after a finite number of steps) can be simulated in space O(s) by a quantum Turing machine (QTM). If the PTM operates with bounded error, then the QTM may be taken to operate with bounded error as well, although the QTM may not halt absolutely in this case. In the unbounded error case, the QTM may be taken to halt absolutely. 2. Any QTM running in space s can be simulated by an unbounded error PTM running in space O(s). No assumptions on the probability of error or Turing time for the QTM are required, but it is assumed that all transition amplitudes of the quantum machine are rational. It follows that unbounded error, space O(s) bounded quantum Turing machines and probabilistic Turing machines are equivalent in power. This implies that any space s QTM can be simulated deterministically in space O(s/sup 2/), and further that any (unbounded-error) QTM running in log-space can be simulated in NC/sup 2/ We also consider quantum analogues of nondeterministic and one-sided error probabilistic space-bounded classes, and prove some simple relationships regarding these classes.
In this paper we study quantum computation from a complexity theoretic viewpoint. Our first result is the existence of an efficient universal quantum Turing machine in Deutsch's model of a quantum Turing machine (QTM) [Proc. Roy. Soc. London Ser. A, 400 (1985), pp. 97--117]. This construction is substantially more complicated than the corresponding construction for classical Turing machines (TMs); in fact, even simple primitives such as looping, branching, and composition are not straightforward in the context of quantum Turing machines. We establish how these familiar primitives can be implemented and introduce some new, purely quantum mechanical primitives, such as changing the computational basis and carrying out an arbitrary unitary transformation of polynomially bounded dimension. We also consider the precision to which the transition amplitudes of a quantum Turing machine need to be specified. We prove that O(log⁡T)O(\log T)O(logT) bits of precision suffice to support a T step computation. This justifies the claim that the quantum Turing machine model should be regarded as a discrete model of computation and not an analog one. We give the first formal evidence that quantum Turing machines violate the modern (complexity theoretic) formulation of the Church--Turing thesis. We show the existence of a problem, relative to an oracle, that can be solved in polynomial time on a quantum Turing machine, but requires superpolynomial time on a bounded-error probabilistic Turing machine, and thus not in the class $\BPP$. The class $\BQP$ of languages that are efficiently decidable (with small error-probability) on a quantum Turing machine satisfies $\BPP \subseteq \BQP \subseteq \Ptime^{\SP}$. Therefore, there is no possibility of giving a mathematical proof that quantum Turing machines are more powerful than classical probabilistic Turing machines (in the unrelativized setting) unless there is a major breakthrough in complexity theory.
How much internal quantum memory is needed to reproduce a stationary stochastic process, and how does reducing that memory change the environmental resources required when output records are retained? This paper establishes exact quantum-source constructions and resource bounds under explicitly specified readout and retained-output conditions. A general completion theorem identifies the minimum Hilbert-space dimension for stationary triple data in the orthogonal-current-symbol source class: it equals the sum of the complex positive-semidefinite ranks of the middle-symbol slices. An attaining construction reproduces the entire canonical stationary order-two process. For the delayed trine process, the minimum classical hidden Markov model requires nine states at every non-independent parameter value. Quantum instruments reproduce the same complete output law using four-dimensional memory throughout the parameter range, with four dimensions proved necessary in a certified low-noise regime and three dimensions both sufficient and necessary on an explicit high-noise interval. The paper then separates reusable memory dimension from environmental dilation cost. On the certified high-noise interval, the exact one-step Pareto frontier consists of a three-dimensional source with recorded-channel Choi rank nine and a four-dimensional source with rank three. Here, Choi rank measures the minimum initially pure environmental remainder dimension for the channel retaining both the emitted classical symbol and final quantum memory. A separate mixed-support qutrit construction at noise parameter 0.99 improves complete-history costs and gives upper bounds close to universal lower bounds. These results show why optimizing a single step need not optimize a retained multi-step history. The analysis also distinguishes complete channels, fixed-input states and archive-only outputs, and demonstrates how access to a retained reference can distinguish generators with identical passive output statistics. Full-word proofs, algebraic complete-positivity certificates, a technical companion and reproducibility materials accompany the results. The exact intermediate memory boundary and complete-history optimum remain open. All results use standard quantum probabilities and apply to the stated operational resource models; they do not establish total hardware, energy or thermodynamic minima.
Readout error models for noisy quantum devices almost universally assume that measurement noise is classical: the measurement statistics are obtained from the ideal computational-basis populations by a column-stochastic assignment matrix AAA. This description is equivalent to assuming that the effective positive-operator-valued measurement (POVM) is diagonal in the measurement basis, and therefore completely insensitive to quantum coherences. We relax this assumption and derive a fully general expression for the observed measurement probabilities under arbitrary completely positive trace-preserving (CPTP) noise preceding a computational-basis measurement. Writing the ideal post-circuit state ρ~\tildeρρ~​ in terms of its populations xxx and coherences yyy, we show that the observed probability vector zzz satisfies z=Ax+Cyz = A x + C yz=Ax+Cy, where AAA is the familiar classical assignment matrix and CCC is a coherence-response matrix constructed from the off-diagonal matrix elements of the effective POVM in the computational basis. The classical model z=Axz = A xz=Ax arises if and only if all POVM elements are diagonal; in this sense CCC quantifies accessible information about coherent readout distortions and interference between computational-basis states, all of which are invisible to models that retain only AAA. Our numerical experiments show that incorporating CCC into readout recovery can improve fidelity over classical inversion and enable selective Pauli twirling with exponentially reduced circuit overhead. This work therefore provides a natural, fully general framework for coherence-sensitive readout modeling on current and future quantum devices.
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.
Abstract. In this paper we study quantum computation from a complexity theoretic viewpoint. Our rst result is the existence of an ecient universal quantum Turing machine in Deutsch’s model of a quantum Turing machine (QTM) [Proc. Roy. Soc. London Ser. A, 400 (1985), pp. 97{117]. This construction is substantially more complicated than the corresponding construction for classical Turing machines (TMs); in fact, even simple primitives such as looping, branching, and composition are not straightforward in the context of quantum Turing machines. We establish how these familiar primitives can be implemented and introduce some new, purely quantum mechanical primitives, such as changing the computational basis and carrying out an arbitrary unitary transformation of polynomially bounded dimension. We also consider the precision to which the transition amplitudes of a quantum Turing machine need to be specied. We prove that O(log T) bits of precision suce to support a T step computation. This justies the claim that the quantum Turing machine model should be regarded as a discrete model of computation and not an analog one. We give the rst formal evidence that quantum Turing machines violate the modern (complexity theoretic) formulation of the Church{Turing thesis. We show the existence of a problem, relative to an oracle, that can be solved in polynomial time on a quantum Turing machine, but requires superpolynomial time on a bounded-error probabilistic Turing machine, and thus not in the class BPP. The class BQP of languages that are eciently decidable (with small error-probability) on a quantum Turing machine satises BPP ⊆ BQP ⊆ P]P. Therefore, there is no possibility of giving a mathematical proof that quantum Turing machines are more powerful than classical probabilistic Turing machines (in the unrelativized setting) unless there is a major breakthrough in complexity theory.