Determining whether a quantum evolution can be efficiently simulated classically is central to understanding the boundary between classical and quantum computation. However, polynomial-time simulability is an asymptotic statement, and does not by itself determine whether the (quantum-inspired) classical simulation is actually practical. Indeed, different polynomial scalings can lead to vastly different computational costs, particularly when expensive preprocessing or quantum data acquisition is required. In this work, we ask whether classically simulable quantum dynamics are in practice more resource-efficient to simulate classically than to execute directly on quantum hardware. We analyze this question using three resource metrics, quantum sample, quantum time, and classical time complexity, for several widely studied classically simulable circuit families. Using representative hardware-level estimates, we identify regimes in which quantum simulation can be faster despite the existence of a polynomial-time classical algorithm, as well as regimes in which classical simulation remains more efficient. At the same time, the large quantum sampling cost needed to characterize unknown input states can make this polynomial-time classical simulation prohibitively expensive with current cloud-based hardware access prices. Ultimately, our work indicates that guarantees of classical simulability with polynomial resources alone are insufficient to determine the preferred implementation.Determining whether a quantum evolution can be efficiently simulated classically is central to understanding the boundary between classical and quantum computation. However, polynomial-time simulability is an asymptotic statement, and does not by itself determine whether the (quantum-inspired) classical simulation is actually practical. Indeed, different polynomial scalings can lead to vastly different computational costs, particularly when expensive preprocessing or quantum data acquisition is required. In this work, we ask whether classically simulable quantum dynamics are in practice more resource-efficient to simulate classically than to execute directly on quantum hardware. We analyze this question using three resource metrics, quantum sample, quantum time, and classical time complexity, for several widely studied classically simulable circuit families. Using representative hardware-level estimates, we identify regimes in which quantum simulation can be faster despite the existence of a polynomial-time classical algorithm, as well as regimes in which classical simulation remains more efficient. At the same time, the large quantum sampling cost needed to characterize unknown input states can make this polynomial-time classical simulation prohibitively expensive with current cloud-based hardware access prices. Ultimately, our work indicates that guarantees of classical simulability with polynomial resources alone are insufficient to determine the preferred implementation.

quant-pharXiv:2609.11847Sep 11, 20260 citations

The threshold for quantum-classical correspondence is $D \sim \hbar^{\frac43}$ The threshold for quantum-classical correspondence is $D \sim \hbar^{\frac43}$

Felipe Hernández, Daniel Ranard, C. Jess Riedel

In chaotic quantum systems, an initially localized quantum state can deviate strongly from the corresponding classical phase-space distribution after the Ehrenfest time $t_{\mathrm{E}} \sim \log(\hbar^{-1})$ , even in the limit $\hbar \to 0$ . Decoherence by the environment is often invoked to explain the persistence of the quantum-classical correspondence at longer timescales. Recent rigorous results for Lindblad dynamics with phase-space diffusion strength $D$ show that quantum and classical evolutions remain close for times that are exponentially longer than the Ehrenfest time whenever $D \gg \hbar^{\frac43}$ , in units set by the classical Hamiltonian. At the same time, some heuristic arguments have suggested the weaker condition $D \gg \hbar^{2}$ always suffices. Here we construct an explicit Lindbladian that demonstrates that the scaling $D \sim \hbar^{\frac43}$ is indeed the threshold for quantum-classical correspondence beyond the Ehrenfest time. Our example uses a smooth time-dependent Hamiltonian and linear Lindblad operators generating homogeneous isotropic diffusion. It exhibits an $\hbar$ -independent quantum-classical discrepancy at the Ehrenfest time whenever $D \ll \hbar^{\frac43}$ , even for $\hbar$ -independent "macroscopic" smooth observables.In chaotic quantum systems, an initially localized quantum state can deviate strongly from the corresponding classical phase-space distribution after the Ehrenfest time $t_{\mathrm{E}} \sim \log(\hbar^{-1})$, even in the limit $\hbar \to 0$. Decoherence by the environment is often invoked to explain the persistence of the quantum-classical correspondence at longer timescales. Recent rigorous results for Lindblad dynamics with phase-space diffusion strength $D$ show that quantum and classical evolutions remain close for times that are exponentially longer than the Ehrenfest time whenever $D \gg \hbar^{\frac43}$, in units set by the classical Hamiltonian. At the same time, some heuristic arguments have suggested the weaker condition $D \gg \hbar^{2}$ always suffices. Here we construct an explicit Lindbladian that demonstrates that the scaling $D \sim \hbar^{\frac43}$ is indeed the threshold for quantum-classical correspondence beyond the Ehrenfest time. Our example uses a smooth time-dependent Hamiltonian and linear Lindblad operators generating homogeneous isotropic diffusion. It exhibits an $\hbar$-independent quantum-classical discrepancy at the Ehrenfest time whenever $D \ll \hbar^{\frac43}$, even for $\hbar$-independent "macroscopic" smooth observables.

quant-pharXiv:2512.17623Dec 22, 20250 citations

Time and Classical and Quantum Mechanics

Peter Lynds

Foundations of Physics LettersFeb 1, 20010 citations

Quantum-Mechanical Time

C. K. Raju

Springer eBooksJan 1, 19945 citations

Improved Classical and Quantum Algorithms for the Shortest Vector Problem via Bounded Distance Decoding

Divesh Aggarwal, Yanlin Chen, Rajendra Kumar +1 more

The most important computational problem on lattices is the Shortest Vector Problem (SVP). In this paper, we present new algorithms that improve the state-of-the-art for provable classical/quantum algorithms for SVP. We present the following results. $\bullet$ A new algorithm for SVP that provides a smooth tradeoff between time complexity and memory requirement. For any positive integer $4\leq q\leq \sqrt{n}$ , our algorithm takes $q^{13n+o(n)}$ time and requires $poly(n)\cdot q^{16n/q^2}$ memory. This tradeoff which ranges from enumeration ( $q=\sqrt{n}$ ) to sieving ( $q$ constant), is a consequence of a new time-memory tradeoff for Discrete Gaussian sampling above the smoothing parameter. $\bullet$ A quantum algorithm for SVP that runs in time $2^{0.950n+o(n)}$ and requires $2^{0.5n+o(n)}$ classical memory and poly(n) qubits. In Quantum Random Access Memory (QRAM) model this algorithm takes only $2^{0.835n+o(n)}$ time and requires a QRAM of size $2^{0.293n+o(n)}$ , poly(n) qubits and $2^{0.5n}$ classical space. This improves over the previously fastest classical (which is also the fastest quantum) algorithm due to [ADRS15] that has a time and space complexity $2^{n+o(n)}$ . $\bullet$ A classical algorithm for SVP that runs in time $2^{1.669n+o(n)}$ time and $2^{0.5n+o(n)}$ space. This improves over an algorithm of [CCL18] that has the same space complexity. The time complexity of our classical and quantum algorithms are obtained using a known upper bound on a quantity related to the lattice kissing number which is $2^{0.402n}$ . We conjecture that for most lattices this quantity is a $2^{o(n)}$ . Assuming that this is the case, our classical algorithm runs in time $2^{1.292n+o(n)}$ , our quantum algorithm runs in time $2^{0.750n+o(n)}$ and our quantum algorithm in QRAM model runs in time $2^{0.667n+o(n)}$ .The most important computational problem on lattices is the Shortest Vector Problem (SVP). In this paper, we present new algorithms that improve the state-of-the-art for provable classical/quantum algorithms for SVP. We present the following results. $\bullet$ A new algorithm for SVP that provides a smooth tradeoff between time complexity and memory requirement. For any positive integer $4\leq q\leq \sqrt{n}$, our algorithm takes $q^{13n+o(n)}$ time and requires $poly(n)\cdot q^{16n/q^2}$ memory. This tradeoff which ranges from enumeration ($q=\sqrt{n}$) to sieving ($q$ constant), is a consequence of a new time-memory tradeoff for Discrete Gaussian sampling above the smoothing parameter. $\bullet$ A quantum algorithm for SVP that runs in time $2^{0.950n+o(n)}$ and requires $2^{0.5n+o(n)}$ classical memory and poly(n) qubits. In Quantum Random Access Memory (QRAM) model this algorithm takes only $2^{0.835n+o(n)}$ time and requires a QRAM of size $2^{0.293n+o(n)}$, poly(n) qubits and $2^{0.5n}$ classical space. This improves over the previously fastest classical (which is also the fastest quantum) algorithm due to [ADRS15] that has a time and space complexity $2^{n+o(n)}$. $\bullet$ A classical algorithm for SVP that runs in time $2^{1.669n+o(n)}$ time and $2^{0.5n+o(n)}$ space. This improves over an algorithm of [CCL18] that has the same space complexity. The time complexity of our classical and quantum algorithms are obtained using a known upper bound on a quantity related to the lattice kissing number which is $2^{0.402n}$. We conjecture that for most lattices this quantity is a $2^{o(n)}$. Assuming that this is the case, our classical algorithm runs in time $2^{1.292n+o(n)}$, our quantum algorithm runs in time $2^{0.750n+o(n)}$ and our quantum algorithm in QRAM model runs in time $2^{0.667n+o(n)}$.

arXiv:2002.07955Feb 19, 20206 citations

Time, Quantum and Information

L. Castell, Otfried Ischebeck

Springer eBooksJan 1, 200355 citations

The threshold for quantum-classical correspondence is

D \sim \hbar^{\frac43}

In chaotic quantum systems, an initially localized quantum state can deviate strongly from the corresponding classical phase-space distribution after the Ehrenfest time

t_{\mathrm{E}} \sim \log(\hbar^{-1})

, even in the limit

\hbar \to 0

. Decoherence by the environment is often invoked to explain the persistence of the quantum-classical correspondence at longer timescales. Recent rigorous results for Lindblad dynamics with phase-space diffusion strength

D

show that quantum and classical evolutions remain close for times that are exponentially longer than the Ehrenfest time whenever

D \gg \hbar^{\frac43}

, in units set by the classical Hamiltonian. At the same time, some heuristic arguments have suggested the weaker condition

D \gg \hbar^{2}

always suffices. Here we construct an explicit Lindbladian that demonstrates that the scaling

D \sim \hbar^{\frac43}

is indeed the threshold for quantum-classical correspondence beyond the Ehrenfest time. Our example uses a smooth time-dependent Hamiltonian and linear Lindblad operators generating homogeneous isotropic diffusion. It exhibits an

\hbar

-independent quantum-classical discrepancy at the Ehrenfest time whenever

D \ll \hbar^{\frac43}

, even for

\hbar

-independent "macroscopic" smooth observables.

\bullet

A new algorithm for SVP that provides a smooth tradeoff between time complexity and memory requirement. For any positive integer

4\leq q\leq \sqrt{n}

, our algorithm takes

q^{13n+o(n)}

time and requires

poly(n)\cdot q^{16n/q^2}

memory. This tradeoff which ranges from enumeration (

q=\sqrt{n}

) to sieving (

q

constant), is a consequence of a new time-memory tradeoff for Discrete Gaussian sampling above the smoothing parameter.

\bullet

A quantum algorithm for SVP that runs in time

2^{0.950n+o(n)}

and requires

2^{0.5n+o(n)}

classical memory and poly(n) qubits. In Quantum Random Access Memory (QRAM) model this algorithm takes only

2^{0.835n+o(n)}

time and requires a QRAM of size

2^{0.293n+o(n)}

, poly(n) qubits and

2^{0.5n}

classical space. This improves over the previously fastest classical (which is also the fastest quantum) algorithm due to [ADRS15] that has a time and space complexity

2^{n+o(n)}

\bullet

A classical algorithm for SVP that runs in time

2^{1.669n+o(n)}

time and

2^{0.5n+o(n)}

space. This improves over an algorithm of [CCL18] that has the same space complexity. The time complexity of our classical and quantum algorithms are obtained using a known upper bound on a quantity related to the lattice kissing number which is

2^{0.402n}

. We conjecture that for most lattices this quantity is a

2^{o(n)}

. Assuming that this is the case, our classical algorithm runs in time

2^{1.292n+o(n)}

, our quantum algorithm runs in time

2^{0.750n+o(n)}

and our quantum algorithm in QRAM model runs in time

2^{0.667n+o(n)}