Despite the development of increasingly capable quantum computers, an experimental demonstration of a provable algorithmic quantum speedup employing today's non-fault-tolerant devices has remained elusive. Here, we unequivocally demonstrate such a speedup within the oracular model, quantified in terms of the scaling with the problem size of the time-to-solution metric. We implement the single-shot Bernstein-Vazirani algorithm, which solves the problem of identifying a hidden bitstring that changes after every oracle query, using two different 27-qubit IBM Quantum superconducting processors. The speedup is observed on only one of the two processors when the quantum computation is protected by dynamical decoupling but not without it. The quantum speedup reported here does not rely on any additional assumptions or complexity-theoretic conjectures and solves a bona fide computational problem in the setting of a game with an oracle and a verifier.
Despite the development of increasingly capable quantum computers, an experimental demonstration of a provable algorithmic quantum speedup employing today's non-fault-tolerant devices has remained elusive. Here, we unequivocally demonstrate such a speedup within the oracular model, quantified in terms of the scaling with the problem size of the time-to-solution metric. We implement the single-shot Bernstein-Vazirani algorithm, which solves the problem of identifying a hidden bitstring that changes after every oracle query, using two different 27-qubit IBM Quantum superconducting processors. The speedup is observed on only one of the two processors when the quantum computation is protected by dynamical decoupling but not without it. The quantum speedup reported here does not rely on any additional assumptions or complexity-theoretic conjectures and solves a bona fide computational problem in the setting of a game with an oracle and a verifier.
Quantum algorithms can outperform their classical counterparts in various tasks, the most prominent example being Shor's algorithm for efficient prime factorization on a quantum computer. It is clear that one of the reasons for the speedup is the superposition principle of quantum mechanics, which allows a quantum processor to be in a superposition of different states at the same time. While such a superposition can lead to entanglement across different qubits of the processors, there also exist quantum algorithms that outperform classical ones using superpositions of individual qubits without entangling them. As an example, the Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle. While the classical version of the algorithm requires multiple calls of the oracle to learn the bit string, a single query of the oracle is enough in the quantum case. In this article, we analyze in detail the quantum resources in the Bernstein-Vazirani algorithm. For this, we introduce and study its probabilistic version, where the goal is to guess the bit string after a single call of the oracle. We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state. We further demonstrate that a large amount of entanglement in the initial state prevents the algorithm from achieving optimal performance. We also apply our methods to quantum computation with mixed states, proving that pseudopure states achieve optimal performance for a given purity in the Bernstein-Vazirani algorithm. We further investigate quantum resources in the one clean qubit model, showing that the model can exhibit speedup over any known classical algorithm even with an arbitrarily little amount of multipartite entanglement, general quantum correlations, and coherence.
Oracle-based quantum computation reframes efficiency from classical time/space costs to query complexity, i.e., the number of accesses to a black-box unitary oracle Uf needed to reveal a hidden property or target state. This study comparatively analyzes query complexity across four canonical oracle-driven algorithms—Deutsch’s, Bernstein–Vazirani, Grover’s search, and Amplitude Amplification—to clarify how superposition, entanglement, interference, and phase kickback translate into provable speedups independent of hardware details. The objective is to systematically connect oracle structure to achievable quantum advantage by contrasting exact, single-query interference algorithms with iterative, probabilistic rotation-based algorithms, and by benchmarking classical deterministic/probabilistic query requirements against quantum bounds. Methodologically, we (i) mathematically model Deutsch and Bernstein–Vazirani via stepwise state-vector evolution to expose phase kickback and phase-encoded answer extraction in one oracle call, (ii) geometrically track Grover and Amplitude Amplification as two-dimensional state-space rotations, quantifying how repeated oracle-driven reflections amplify success amplitude, and (iii) compute classical query baselines and compare them directly with quantum query scaling. Results show that Deutsch reduces classical 2 queries to exactly 1 quantum query for constant-versus-balanced testing, while Bernstein–Vazirani deterministically recovers an n-bit hidden string s with (O(1)) quantum queries versus (O(n)) classical queries. For unstructured search over (N=2n) items, Grover achieves a bounded-error quadratic improvement from (O(N)) to (O(√{N}) queries, and Amplitude Amplification generalizes this to boost success probability from (p) to near certainty in O (1/√p) oracle applications. The central implication is a structural divide: rigid algebraic structure permits maximal, single-query speedups, whereas unstructured “chaos” necessitates iterative geometric amplification, which is more broadly applicable but demands highly stable, error-corrected hardware; consequently, quantum systems are best viewed as specialized co-processors activated when oracle structure warrants a quantum shortcut.
Abstract This study presents practical experience implementing the Bernstein–Vazirani algorithm on the IBM Q quantum computing platform, focusing on energy-efficient and reversible computation guided by Landauer’s principle. The work highlights the role of fundamental quantum logic gates—including CNOT, NOT, CCNOT, OR, and XOR—in constructing scalable, reversible circuits. By applying these principles, the Bernstein–Vazirani algorithm demonstrates an efficient solution to the problem of determining a hidden binary vector with a minimal number of queries, showcasing the potential for quantum computational speedup and optimization of information processing. The research emphasizes the importance of reversible quantum operations in improving computational efficiency and expanding the capabilities of modern quantum systems.
This presentation gives a comprehensive overview of quantum query algorithms, beginning with an introduction to the query model of computation where input is accessed via an oracle function. It then details several foundational quantum algorithms that demonstrate a quantum advantage over classical approaches: Deutsch's problem is solved with a single query using phase kickback to determine if a function is constant or balanced; the Deutsch-Jozsa algorithm extends this to n-bit inputs, efficiently distinguishing constant from balanced functions with one query versus an exponential need classically; the Bernstein-Vazirani algorithm identifies a hidden string with one query, outperforming classical linear requirements; and Simon's algorithm, which finds a hidden period in a two-to-one function with a linear number of queries, showcases an exponential speedup over the best classical probabilistic algorithms.
The complexity of certain classical computer algorithms can be reduced by a quantum algorithm completing the same task. We examine the implementation of the Bernstein–Vazirani algorithm. It finds the hidden n-bit string s from the function fs(x)=sx that takes an n-bit input string x and outputs one bit, the dot product. This algorithm reduces the complexity from n queries for the best classical algorithm to just one. Though the quantum algorithm theoretically always gives the correct string, in practice, factors such as decoherence of the physical qubits due to external noise reduce the algorithm’s accuracy. By implementing the algorithm on the IBM 5-qubit and 14-qubit quantum computers, we are able to analyze correlations between the accuracy of the results and the properties of the physical qubits used. Not all qubits are pairwise connected, nor do they have the same coherence times. Using Python to build the quantum circuits, we create several implementations of the circuit with different qubits. We establish that 1/T1, 1/T2, and gate errors are positively correlated with calculation errors. Consequently, we observe that the 14-qubit quantum computer, on average, is more prone to errors than the 5-qubit quantum computer.
Dynamical decoupling (DD) is a low-overhead method for quantum error suppression. Despite extensive work in DD design, finding pulse sequences that optimally decouple computational qubits is not well understood. Using IBM’s superconducting-qubit-based quantum processors, we demonstrate how to empirically tailor DD strategies for an arbitrary quantum circuit and device. These learned DD strategies significantly improve error suppression relative to canonical sequences, with relative improvement increasing with problem size and circuit sophistication. We leverage this to study mirror randomized benchmarking on 100 qubits, Greenberger-Horne-Zeilinger state preparation on 50 qubits, and the Bernstein-Vazirani algorithm on 27 qubits. Our empirical learning method finds strategies, in constant time independent of circuit width and depth, provides stable performance over long time periods without retraining, and generalizes to larger circuits when trained on small subcircuit structures.