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:1605.03534 · Annals of Physics

Time, classical and quantum

P. Aniello, Florio M. Ciaglia, Fabio Di Cosmo, G. Marmo, Juan Manuel Pérez-Pardo

Published Aug 6, 2016• 9 citations
arXivHTMLPDF
DOI
10.1016/j.aop.2016.08.001

Related papers

The cost of simulating classically tractable quantum circuits and dynamics

Su Yeon Chang, Supanut Thanasilp, Zoë Holmes +1 more

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.11847•Sep 11, 2026•2 citations

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.

quant-pharXiv:2512.17623•Dec 22, 2025•1 citation

Time and Classical and Quantum Mechanics

Peter Lynds

Foundations of Physics Letters•Feb 1, 2001•0 citations

Quantum-Mechanical Time

C. K. Raju

Springer eBooks•Jan 1, 1994•5 citations

Time and the Quantum World

Klaus Mainzer

Springer eBooks•Jan 1, 2002•0 citations

Another subexponential-time quantum algorithm for the dihedral hidden subgroup problem

Greg Kuperberg

We give an algorithm for the hidden subgroup problem for the dihedral group $D_N$, or equivalently the cyclic hidden shift problem, that supersedes our first algorithm and is suggested by Regev's algorithm. It runs in $\exp(O(\sqrt{\log N}))$ quantum time and uses $\exp(O(\sqrt{\log N}))$ classical space, but only $O(\log N)$ quantum space. The algorithm also runs faster with quantumly addressable classical space than with fully classical space. In the hidden shift form, which is more natural for this algorithm regardless, it can also make use of multiple hidden shifts. It can also be extended with two parameters that trade classical space and classical time for quantum time. At the extreme space-saving end, the algorithm becomes Regev's algorithm. At the other end, if the algorithm is allowed classical memory with quantum random access, then many trade-offs between classical and quantum time are possible.

arXiv:1112.3333•Dec 14, 2011•73 citations
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.
The threshold for quantum-classical correspondence is D∼ℏ43D \sim \hbar^{\frac43}D∼ℏ34​
In chaotic quantum systems, an initially localized quantum state can deviate strongly from the corresponding classical phase-space distribution after the Ehrenfest time tE∼log⁡(ℏ−1)t_{\mathrm{E}} \sim \log(\hbar^{-1})tE​∼log(ℏ−1), even in the limit ℏ→0\hbar \to 0ℏ→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 DDD show that quantum and classical evolutions remain close for times that are exponentially longer than the Ehrenfest time whenever D≫ℏ43D \gg \hbar^{\frac43}D≫ℏ34​, in units set by the classical Hamiltonian. At the same time, some heuristic arguments have suggested the weaker condition D≫ℏ2D \gg \hbar^{2}D≫ℏ2 always suffices. Here we construct an explicit Lindbladian that demonstrates that the scaling D∼ℏ43D \sim \hbar^{\frac43}D∼ℏ34​ 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≪ℏ43D \ll \hbar^{\frac43}D≪ℏ34​, even for ℏ\hbarℏ-independent "macroscopic" smooth observables.
We give an algorithm for the hidden subgroup problem for the dihedral group DND_NDN​, or equivalently the cyclic hidden shift problem, that supersedes our first algorithm and is suggested by Regev's algorithm. It runs in exp⁡(O(log⁡N))\exp(O(\sqrt{\log N}))exp(O(logN​)) quantum time and uses exp⁡(O(log⁡N))\exp(O(\sqrt{\log N}))exp(O(logN​)) classical space, but only O(log⁡N)O(\log N)O(logN) quantum space. The algorithm also runs faster with quantumly addressable classical space than with fully classical space. In the hidden shift form, which is more natural for this algorithm regardless, it can also make use of multiple hidden shifts. It can also be extended with two parameters that trade classical space and classical time for quantum time. At the extreme space-saving end, the algorithm becomes Regev's algorithm. At the other end, if the algorithm is allowed classical memory with quantum random access, then many trade-offs between classical and quantum time are possible.