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:2008.06478 · Nature Physics

Quantum advantage for computations with limited space

Dmitri Maslov, Jin-Sung Kim, Sergey B. Bravyi, Theodore J. Yoder, Sarah Sheldon

Published Jun 28, 2021• 39 citations
arXivHTMLPDF
DOI
10.1038/s41567-021-01271-7

Related papers

CLASSICAL AND QUANTUM COMPUTATION WITH SMALL SPACE BOUNDS

Abuzer Yakarylmaz

•Jan 1, 2011•8 citations

Phase Coordinate Uncomputation in Quantum Recursive Fourier Sampling

Christoffer Hindlycke, Niklas Johansson, Jan-Åke Larsson

Recursive Fourier Sampling (RFS) was one of the earliest problems to demonstrate a quantum advantage, and is known to lie outside the Merlin-Arthur complexity class. This work contains a new description of quantum algorithms in phase space terminology, demonstrating its use in RFS, and how and why this gives a better understanding of the quantum advantage in RFS. Most importantly, describing the computational process of quantum computation in phase space terminology gives a much better understanding of why uncomputation is necessary when solving RFS: the advantage is present only when phase coordinate garbage is uncomputed. This is the underlying reason for the limitations of the quantum advantage.

arXiv:2408.15938•Entropy•Jun 2, 2025•1 citation

A Structural Theory of Quantum Computational Advantage from Admissible Histories

Bin Li

We propose a structural framework for interpreting quantum computational advantage in terms of admissible continuation of configurations. In this framework, a quantum computation is described not only as a sequence of gates acting on a state vector but also as the organization of admissible histories whose phase contributions combine coherently in a manner related to sum-over-histories and path-integral formulations of quantum mechanics. We identify three structural features that are relevant to quantum advantage: the multiplicity of admissible histories, the degree of phase coherence among them, and the non-factorizable structure of continuation constraints corresponding to entanglement-like global dependence. To make these features explicit, we introduce the notion of effective coherent multiplicity, which measures the coherently usable portion of an admissible-history space before probability normalization. We then formulate a structural speedup conjecture: substantial quantum advantage requires not merely a large number of possible histories but scalable coherent multiplicity supported by non-factorizable constraints whose instability remains bounded. We also introduce a coherent-fiber criterion, which identifies phase-alignable families of histories selected by compact computational relations as a structural source of coherent amplification. This formulation does not replace standard complexity-theoretic measures such as circuit size, query complexity, or BQP membership. Rather, it provides a complementary structural language for relating those measures to interference, entanglement, decoherence, and the organization of computational history space. The framework clarifies, at a structural level, why raw branching alone is insufficient for speedup, why unstructured search yields only a limited advantage, and why problems with compact global regularities, such as Simon’s problem and period finding, can support stronger coherent amplification. The paper also discusses how the proposed quantities relate to standard notions, including success amplitudes, entanglement measures, tensor-network simulability, and fault-tolerance constraints. In this way, admissible-history structure is presented as a diagnostic viewpoint for understanding both the power and limitations of quantum computation.

Quantum Reports•May 22, 2026•1 citation

Quantum Computing: General Considerations

David S. Simon

Undergraduate texts in physics•Jan 1, 2025•0 citations

Quantum Computing and its Efficiency

Srajit Mehrotra

International Journal of Scientific and Engineering Research•Oct 25, 2017•0 citations

Quantum Advantage Actor-Critic for Reinforcement Learning

Michael Kölle, Mohamad Hgog, Fabian Ritz +4 more

Quantum computing offers efficient encapsulation of high-dimensional states. In this work, we propose a novel quantum reinforcement learning approach that combines the Advantage Actor-Critic algorithm with variational quantum circuits by substituting parts of the classical components. This approach addresses reinforcement learning's scalability concerns while maintaining high performance. We empirically test multiple quantum Advantage Actor-Critic configurations with the well known Cart Pole environment to evaluate our approach in control tasks with continuous state spaces. Our results indicate that the hybrid strategy of using either a quantum actor or quantum critic with classical post-processing yields a substantial performance increase compared to pure classical and pure quantum variants with similar parameter counts. They further reveal the limits of current quantum approaches due to the hardware constraints of noisy intermediate-scale quantum computers, suggesting further research to scale hybrid approaches for larger and more complex control tasks.

arXiv:2401.07043•International Conference on Agents and Artificial Intelligence (ICAART)•Jan 1, 2024•30 citations
Recursive Fourier Sampling (RFS) was one of the earliest problems to demonstrate a quantum advantage, and is known to lie outside the Merlin-Arthur complexity class. This work contains a new description of quantum algorithms in phase space terminology, demonstrating its use in RFS, and how and why this gives a better understanding of the quantum advantage in RFS. Most importantly, describing the computational process of quantum computation in phase space terminology gives a much better understanding of why uncomputation is necessary when solving RFS: the advantage is present only when phase coordinate garbage is uncomputed. This is the underlying reason for the limitations of the quantum advantage.
We propose a structural framework for interpreting quantum computational advantage in terms of admissible continuation of configurations. In this framework, a quantum computation is described not only as a sequence of gates acting on a state vector but also as the organization of admissible histories whose phase contributions combine coherently in a manner related to sum-over-histories and path-integral formulations of quantum mechanics. We identify three structural features that are relevant to quantum advantage: the multiplicity of admissible histories, the degree of phase coherence among them, and the non-factorizable structure of continuation constraints corresponding to entanglement-like global dependence. To make these features explicit, we introduce the notion of effective coherent multiplicity, which measures the coherently usable portion of an admissible-history space before probability normalization. We then formulate a structural speedup conjecture: substantial quantum advantage requires not merely a large number of possible histories but scalable coherent multiplicity supported by non-factorizable constraints whose instability remains bounded. We also introduce a coherent-fiber criterion, which identifies phase-alignable families of histories selected by compact computational relations as a structural source of coherent amplification. This formulation does not replace standard complexity-theoretic measures such as circuit size, query complexity, or BQP membership. Rather, it provides a complementary structural language for relating those measures to interference, entanglement, decoherence, and the organization of computational history space. The framework clarifies, at a structural level, why raw branching alone is insufficient for speedup, why unstructured search yields only a limited advantage, and why problems with compact global regularities, such as Simon’s problem and period finding, can support stronger coherent amplification. The paper also discusses how the proposed quantities relate to standard notions, including success amplitudes, entanglement measures, tensor-network simulability, and fault-tolerance constraints. In this way, admissible-history structure is presented as a diagnostic viewpoint for understanding both the power and limitations of quantum computation.
Quantum computing offers efficient encapsulation of high-dimensional states. In this work, we propose a novel quantum reinforcement learning approach that combines the Advantage Actor-Critic algorithm with variational quantum circuits by substituting parts of the classical components. This approach addresses reinforcement learning's scalability concerns while maintaining high performance. We empirically test multiple quantum Advantage Actor-Critic configurations with the well known Cart Pole environment to evaluate our approach in control tasks with continuous state spaces. Our results indicate that the hybrid strategy of using either a quantum actor or quantum critic with classical post-processing yields a substantial performance increase compared to pure classical and pure quantum variants with similar parameter counts. They further reveal the limits of current quantum approaches due to the hardware constraints of noisy intermediate-scale quantum computers, suggesting further research to scale hybrid approaches for larger and more complex control tasks.