Quantum Simulation Logic, Oracles, and the Quantum Advantage

Abstract

Query complexity is a common tool for comparing quantum and classical computation, and it has produced many examples of how quantum algorithms differ from classical ones. Here we investigate in detail the role that oracles play for the advantage of quantum algorithms. We do so by using a simulation framework, Quantum Simulation Logic (QSL), to construct oracles and algorithms that solve some problems with the same success probability and number of queries as the quantum algorithms. The framework can be simulated using only classical resources at a constant overhead as compared to the quantum resources used in quantum computation. Our results clarify the assumptions made and the conditions needed when using quantum oracles. Using the same assumptions on oracles within the simulation framework we show that for some specific algorithms, like the Deutsch-Jozsa and Simon's algorithms, there simply is no advantage in terms of query complexity. This does not detract from the fact that quantum query complexity provides examples of how a quantum computer can be expected to behave, which in turn has proved useful for finding new quantum algorithms outside of the oracle paradigm, where the most prominent example is Shor's algorithm for integer factorization.

arXiv comment48 pages, 46 figures

References in corpus (38)

• Entanglement of Formation of an Arbitrary State of Two Qubits
• Quantum cryptography: Public key distribution and coin tossing
• Quantifying Coherence
• Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance
• Improved Simulation of Stabilizer Circuits
• Strengths and Weaknesses of Quantum Computing
• Quantum Algorithms Revisited
• Universal state inversion and concurrence in arbitrary dimensions
• In defense of the epistemic view of quantum states: a toy theory
• Contextuality supplies the magic for quantum computation
• Realization of a scalable Shor algorithm
• Shor's quantum factoring algorithm on a photonic chip
• Semiclassical Fourier Transform for Quantum Computation
• Experimental realisation of Shor's quantum factoring algorithm using qubit recycling
• Breaking Symmetric Cryptosystems using Quantum Period Finding
• Experimental demonstration of Shor's algorithm with quantum entanglement
• Computing prime factors with a Josephson phase qubit quantum processor
• Coherence as a resource in decision problems: The Deutsch-Jozsa algorithm and a variation
• Demonstration of Shor's quantum factoring algorithm using photonic qubits
• Efficient Networks for Quantum Factoring
• An Exact Quantum Polynomial-Time Algorithm for Simon's Problem
• Complete 3-Qubit Grover Search on a Programmable Quantum Computer
• The completeness of quantum theory for predicting measurement outcomes
• Quasi-quantization: classical statistical theories with an epistemic restriction
• Quantum from principles
• Introduction to the book "Quantum Theory: Informational Foundations and Foils"
• Deutsch-Jozsa algorithm as a test of quantum computation
• Pretending to factor large numbers on a quantum computer
• Three ways to look at mutually unbiased bases
• Translation of Lueders' "Uber die Zustandsanderung durch den Messprozess"
• Memory cost of quantum contextuality
• "No Information Without Disturbance": Quantum Limitations of Measurement
• Experimental Realization of a One-way Quantum Computer Algorithm Solving Simon's Problem
• Efficient classical simulation of the Deutsch-Jozsa and Simon's algorithms
• Stabilizer notation for Spekkens' toy theory
• Sequences of projective measurements in generalized probabilistic models
• The Deutsch-Jozsa Problem: De-quantisation and Entanglement
• On the epistemic view of quantum states

Cited by in corpus (6)

• Kochen-Specker Contextuality
• Nonlinear Quantum Neuron: A Fundamental Building Block for Quantum Neural Networks
• Efficient contextual ontological model of $n$-qubit stabilizer quantum mechanics
• Dirac formulation for universal quantum gates and Shor's integer factorization in high-frequency electric circuits
• Phase Coordinate Uncomputation in Quantum Recursive Fourier Sampling
• Conjugate Logic