The oracle model of computation is believed to allow a rigorous proof of quantum over classical computational superiority. Since quantum and classical oracles are essentially different, a correspondence principle is commonly implicitly used as a platform for comparison of oracle complexity. Here, we question the grounds on which this correspondence is based. Obviously, results on quantum speed-up depend on the chosen correspondence. So, we introduce the notion of genuine quantum speed-up which can serve as a tool for reliable comparison of quantum vs classical complexity, independently of the chosen correspondence principle.
The oracle model of computation is believed to allow a rigorous proof of quantum over classical computational superiority. Since quantum and classical oracles are essentially different, a correspondence principle is commonly implicitly used as a platform for comparison of oracle complexity. Here, we question the grounds on which this correspondence is based. Obviously, results on quantum speed-up depend on the chosen correspondence. So, we introduce the notion of genuine quantum speed-up which can serve as a tool for reliable comparison of quantum vs classical complexity, independently of the chosen correspondence principle.
The oracle model of computation is believed to allow a rigorous proof of quantum over classical computational superiority. Since quantum and classical oracles are essentially different, a correspondence principle is commonly implicitly used as a platform for comparison of oracle complexity. Here, we question the grounds on which this correspondence is based. Obviously, results on quantum speed-up depend on the chosen correspondence. So, we introduce the notion of genuine quantum speed-up which can serve as a tool for reliable comparison of quantum versus classical complexity, independent of the chosen correspondence principle.
An important theoretical problem in the study of quantum computation, that is also practically relevant in the context of near-term quantum devices, is to understand the computational power of hybrid models, that combine poly-time classical computation with short-depth quantum computation. Here, we consider two such models: CQ_d which captures the scenario of a polynomial-time classical algorithm that queries a d-depth quantum computer many times; and QC_d which is more analogous to measurement-based quantum computation and captures the scenario of a d-depth quantum computer with the ability to change the sequence of gates being applied depending on measurement outcomes processed by a classical computation. Chia, Chung & Lai (STOC 2020) and Coudron & Menda (STOC 2020) showed that these models (with d=log^O(1) (n)) are strictly weaker than BQP (the class of problems solvable by poly-time quantum computation), relative to an oracle, disproving a conjecture of Jozsa in the relativised world. We show that, despite the similarities between CQ_d and QC_d, the two models are incomparable, i.e. CQ_d ⊈ QC_d and QC_d ⊈ CQ_d relative to an oracle. In other words, there exist problems that one model can solve but not the other and vice versa. We do this by considering new oracle problems that capture the distinctions between the two models and by introducing the notion of an intrinsically stochastic oracle, an oracle whose responses are inherently randomised, which is used for our second result. While we leave showing the second separation relative to a standard oracle as an open problem, we believe the notion of stochastic oracles could be of independent interest for studying complexity classes which have resisted separation in the standard oracle model. Our constructions also yield simpler oracle separations between the hybrid models and BQP, compared to earlier works.
In this thesis we address the question, what is the resource, or property, that enables the advantage of quantum computers?The theory of quantum computers dates back to the eighties, so one would think there already is an answer to this question.There are several proposed solutions, but to this date, there is no consensus on an answer.Primarily, the advantage of quantum computers is characterized by a speedup for certain computational problems.This speedup is measured by comparing quantum algorithms with the bestknown classical algorithms.For some algorithms we assume access to an object called oracle.The oracle computes a function, and the complexity of the oracle is of no concern.Instead, we count the number of queries to the oracle needed to solve the problem.Informally, the question we ask using an oracle is: if we can compute this function efficiently, what else could we then compute.However, using oracles while measuring a quantum speedup, we assume access to vastly different oracles residing in different models of computation.For our investigation of the speedup, we introduce a classical simulation framework that imitates quantum algorithms.The simulation suggests that the property enabling the potential quantum speedup is the ability to store, process, and retrieve information in an additional degree of freedom.We then theoretically verified that this is true for all problems that can be efficiently solved with a quantum computer.In parallel to this, we also see that quantum oracles sharply specify the information we can retrieve from the additional degree of freedom, while regular oracles do not.A regular oracle does not even allow for an extra degree of freedom.We conclude that comparing quantum with classical oracle query complexity bounds does not provide conclusive evidence for a quantum advantage.I want to thank Jan-Åke Larsson, without whom this research would not have been possible.If there is any magic in the world, it shows through Jan-Åke's ability to simultaneously be a good supervisor, colleague, and friend.I would also like to thank my co-supervisor Peter Jonsson, for many valuable discussions -not only restricted to theoretical computer science.To my friends and collogues that have challenged me to become better, especially Jonathan Jogenfors
Abstract This guide is based on the IBM Quantum course Quantum Algorithmic Foundations and addresses a central question in quantum computation: Do quantum algorithms offer provable advantages beyond the oracle (black-box) query model, in more standard computational settings where inputs are given explicitly? Answering this question requires building a rigorous theoretical foundation. The course begins with a detailed discussion of computational cost in both classical and quantum models, focusing on how complexity scales with input size rather than on absolute execution time. The emphasis is placed on algorithmic efficiency, independent of hardware improvements. To ground the discussion, the material draws heavily from computational number theory, including problems such as: Integer arithmetic Greatest common divisor (GCD) computation Integer factorization Although number theory represents a specific application domain, it provides a clear and powerful framework for analyzing computational complexity and illustrating the principles underlying quantum speedups. A key theme of the lesson is the distinction between algorithmic scalability and hardware performance. The primary concern is how the cost of an algorithm grows as problem instances become larger — a perspective that remains valid across technological generations. The course concludes by addressing a critically important concept: implementing classical computations on quantum computers. The significance of this idea is not to replace classical machines, but to use classical algorithms as subroutines within quantum procedures. This hybrid approach leverages decades of classical algorithmic research while opening new pathways toward quantum computational advantage. Through practical experimentation on IBM Q, this work connects theoretical foundations with hands-on quantum programming, reinforcing the structural principles that underlie advanced quantum algorithm design.
Since the introduction of the complexity class QMA as a quantum-verifier analogue of NP (Kitaev, 1997), many have wondered whether quantum proofs are necessary or classical proofs suffice - that is, whether QMA = QCMA or QCMA != QMA (Aharonov and Naveh, 2002; Aaronson and Kuperberg, CCC '07). This longstanding question was recently answered by works of Bostanci, Haferkamp, Nirkhe, and Zhandry (STOC '26) and Bostanci, Huang, and Vaikuntanathan (FOCS '26), which showed that quantum proofs are more powerful than classical ones in the classical-oracle setting.
However, it remains unclear what exactly makes quantum proofs more powerful than classical ones. In the information-theoretic setting, a family of quantum states is not classicalizable if and only if it is unclonable. Indeed, these recent works also explicitly highlight the unclonability of their quantum proofs as a key mechanism behind their separations, and their arguments crucially rely on this property. This raises the question of whether unclonability is necessary for quantum proofs to be more powerful than classical ones.
In this work, we show that even clonable quantum proofs can be more powerful than classical ones relative to a classical oracle by constructing a classical oracle O such that QCMA^O != ClonableQMA^O. This resolves the open question of Nehoran and Zhandry (ITCS '24), who established the analogous separation relative to a quantum oracle. We also show a classical-oracle separation between BQP/clonableqpoly and BQP/poly, and give applications of our results to quantum cryptography.