DROPS

Document

DOI: 10.4230/LIPIcs.CCC.2025.5

Improved Separation Between Quantum and Classical Computers for Sampling and Functional Tasks

Authors: Simon C. Marshall, Scott Aaronson, and Vedran Dunjko

Published in: LIPIcs, Volume 339, 40th Computational Complexity Conference (CCC 2025)

Abstract

This paper furthers existing evidence that quantum computers are capable of computations beyond classical computers. Specifically, we strengthen the collapse of the polynomial hierarchy to the second level if: (i) Quantum computers with postselection are as powerful as classical computers with postselection (PostBQP = PostBPP), (ii) any one of several quantum sampling experiments (BosonSampling, IQP, DQC1) can be approximately performed by a classical computer (contingent on existing assumptions). This last result implies that if any of these experiment’s hardness conjectures hold, then quantum computers can implement functions classical computers cannot (FBQP≠ FBPP) unless the polynomial hierarchy collapses to its 2nd level. These results are an improvement over previous work which either achieved a collapse to the third level or were concerned with exact sampling, a physically impractical case. The workhorse of these results is a new technical complexity-theoretic result which we believe could have value beyond quantum computation. In particular, we prove that if there exists an equivalence between problems solvable with an exact counting oracle and problems solvable with an approximate counting oracle, then the polynomial hierarchy collapses to its second level, indeed to ZPP^NP.

Cite as

Simon C. Marshall, Scott Aaronson, and Vedran Dunjko. Improved Separation Between Quantum and Classical Computers for Sampling and Functional Tasks. In 40th Computational Complexity Conference (CCC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 339, pp. 5:1-5:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{marshall_et_al:LIPIcs.CCC.2025.5,
  author =	{Marshall, Simon C. and Aaronson, Scott and Dunjko, Vedran},
  title =	{{Improved Separation Between Quantum and Classical Computers for Sampling and Functional Tasks}},
  booktitle =	{40th Computational Complexity Conference (CCC 2025)},
  pages =	{5:1--5:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-379-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{339},
  editor =	{Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2025.5},
  URN =		{urn:nbn:de:0030-drops-236991},
  doi =		{10.4230/LIPIcs.CCC.2025.5},
  annote =	{Keywords: Quantum advantage, Approximate counting, Boson sampling}
}

Document

DOI: 10.4230/LIPIcs.TQC.2023.13

Quantum Policy Gradient Algorithms

Authors: Sofiene Jerbi, Arjan Cornelissen, Maris Ozols, and Vedran Dunjko

Published in: LIPIcs, Volume 266, 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)

Abstract

Understanding the power and limitations of quantum access to data in machine learning tasks is primordial to assess the potential of quantum computing in artificial intelligence. Previous works have already shown that speed-ups in learning are possible when given quantum access to reinforcement learning environments. Yet, the applicability of quantum algorithms in this setting remains very limited, notably in environments with large state and action spaces. In this work, we design quantum algorithms to train state-of-the-art reinforcement learning policies by exploiting quantum interactions with an environment. However, these algorithms only offer full quadratic speed-ups in sample complexity over their classical analogs when the trained policies satisfy some regularity conditions. Interestingly, we find that reinforcement learning policies derived from parametrized quantum circuits are well-behaved with respect to these conditions, which showcases the benefit of a fully-quantum reinforcement learning framework.

Cite as

Sofiene Jerbi, Arjan Cornelissen, Maris Ozols, and Vedran Dunjko. Quantum Policy Gradient Algorithms. In 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 266, pp. 13:1-13:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{jerbi_et_al:LIPIcs.TQC.2023.13,
  author =	{Jerbi, Sofiene and Cornelissen, Arjan and Ozols, Maris and Dunjko, Vedran},
  title =	{{Quantum Policy Gradient Algorithms}},
  booktitle =	{18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)},
  pages =	{13:1--13:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-283-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{266},
  editor =	{Fawzi, Omar and Walter, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2023.13},
  URN =		{urn:nbn:de:0030-drops-183230},
  doi =		{10.4230/LIPIcs.TQC.2023.13},
  annote =	{Keywords: quantum reinforcement learning, policy gradient methods, parametrized quantum circuits}
}

Search Results

Documents authored by Dunjko, Vedran

Improved Separation Between Quantum and Classical Computers for Sampling and Functional Tasks

Abstract

Cite as

Quantum Policy Gradient Algorithms

Abstract

Cite as

Thanks for your feedback!

Could not send message