An Exact Quantum Polynomial-Time Algorithm for Simon's Problem

Abstract

We investigate the power of quantum computers when they are required to return an answer that is guaranteed to be correct after a time that is upper-bounded by a polynomial in the worst case. We show that a natural generalization of Simon's problem can be solved in this way, whereas previous algorithms required quantum polynomial time in the expected sense only, without upper bounds on the worst-case running time. This is achieved by generalizing both Simon's and Grover's algorithms and combining them in a novel way. It follows that there is a decision problem that can be solved in exact quantum polynomial time, which would require expected exponential time on any classical bounded-error probabilistic computer if the data is supplied as a black box.

12 pages, LaTeX2e, no figures. To appear in Proceedings of the Fifth Israeli Symposium on Theory of Computing and Systems (ISTCS'97)

References in corpus (3)

• An approximate Fourier transform useful in quantum factoring
• Quantum Physics and Computers
• On The Power of Exact Quantum Polynomial Time

Cited by in corpus (85)

• Quantum Amplitude Amplification and Estimation
• Quantum algorithms: an overview
• Quantum Counting
• Quantum Algorithm for the Collision Problem
• Amplitude estimation without phase estimation
• Sophisticated quantum search without entanglement
• Efficient Distributed Quantum Computing
• A different kind of quantum search
• Emerging quantum computing algorithms for quantum chemistry
• The quantum query complexity of the hidden subgroup problem is polynomial
• Quantum Search on Bounded-Error Inputs
• Noisy intermediate-scale quantum computers
• An Introduction to Quantum Complexity Theory
• Superiority of exact quantum automata for promise problems
• Lower Bounds on Quantum Query Complexity
• Variational quantum amplitude estimation
• Quantum speedup of the Travelling Salesman Problem for bounded-degree graphs
• Imaginary Time Propagation on a Quantum Chip
• Black-box Hamiltonian simulation and unitary implementation
• A Survey of Quantum Property Testing
• On exact quantum query complexity
• Quantum algorithm for Feynman loop integrals
• Bounds for Small-Error and Zero-Error Quantum Algorithms
• Efficient classical simulation of the Deutsch-Jozsa and Simon's algorithms
• Implementation of group-covariant POVMs by orthogonal measurements
• Complexity Classes of Equivalence Problems Revisited
• Quantum Networks for Concentrating Entanglement
• Generalizations of the distributed Deutsch-Jozsa promise problem
• Quantum Error Mitigation Relying on Permutation Filtering
• Quantum algorithms to solve the hidden shift problem for quadratics and for functions of large Gowers norm
• Quantum Simulation Logic, Oracles, and the Quantum Advantage
• Exact quantum query complexity of EXACT and THRESHOLD
• Nondeterministic Quantum Query and Quantum Communication Complexities
• Exhaustive search for optimal molecular geometries using imaginary-time evolution on a quantum computer
• On Quantum Algorithms for Noncommutative Hidden Subgroups
• Sharp Quantum vs. Classical Query Complexity Separations
• Recommendation systems with quantum k-NN and Grover's algorithms for data processing
• Potential of quantum finite automata with exact acceptance
• Quantum Fourier Iterative Amplitude Estimation
• Applications of the Adversary Method in Quantum Query Algorithms
• An Algorithmic Argument for Nonadaptive Query Complexity Lower Bounds on Advised Quantum Computation
• Characterizations of symmetrically partial Boolean functions with exact quantum query complexity
• Quantum Query as a State Decomposition
• Quantum smoothed particle hydrodynamics algorithm inspired by quantum walks
• A Quantum Implementation Model for Artificial Neural Networks
• Exact block encoding of imaginary time evolution with universal quantum neural networks
• Exponential improvements for quantum-accessible reinforcement learning
• Exact quantum query complexity of ${\mathrm{EXACT}}_{\mathrm{k},\mathrm{l}}^{\mathrm{n}}$
• Normalizer Circuits and Quantum Computation
• Deterministic Algorithms for the Hidden Subgroup Problem
• Normalizer circuits and a Gottesman-Knill theorem for infinite-dimensional systems
• Quantum Computing Discrete Logarithms with the Help of a Preprocessed State
• Fixed-point quantum continuous search algorithm with optimal query complexity
• Almost-Everywhere Superiority for Quantum Computing
• Quantum algorithms for solvable groups
• Cosine series quantum sampling method with applications in signal and image processing
• Abelian Hypergroups and Quantum Computation
• Exact quantum algorithms have advantage for almost all Boolean functions
• Efficient quantum algorithms for some instances of the non-Abelian hidden subgroup problem
• Derandomization of quantum algorithm for triangle finding
• Tight Bounds for Inverting Permutations via Compressed Oracle Arguments
• Quantum Realization of the Finite Element Method
• Non-unitary Coupled Cluster Enabled by Mid-circuit Measurements on Quantum Computers
• Superlinear advantage for exact quantum algorithms
• A quantum Goldreich-Levin theorem with cryptographic applications
• Quantum algorithms for shifted subset problems
• Quantum Measurements for Hidden Subgroup Problems with Optimal Sample Complexity
• A new quantum algorithm for the hidden shift problem in ${\mathbb{Z}}_{2^t}^n$
• Quantum Property Testing
• Quantum Computation Relative to Oracles
• Collapse of the Hierarchy of Constant-Depth Exact Quantum Circuits
• Technical Report: Toward Applying Quantum Computing to Network Verification
• On the uselessness of quantum queries
• Quantum Fourier Sampling is Guaranteed to Fail to Compute Automorphism Groups of Easy Graphs
• Early days following Grover's quantum search algorithm
• Memory Efficient Quantum Circuit Simulator Based on Linked List Architecture
• An Optimum Algorithm for Quantum Search
• Explicit decoders using fixed-point amplitude amplification based on QSVT
• Nuclear two point correlation functions on a quantum-computer
• Probabilistic imaginary-time evolution by using forward and backward real-time evolution with a single ancilla: first-quantized eigensolver of quantum chemistry for ground states
• Quantum Heaviside Eigen Solver
• Reversible Mapping for Tree Structured Quantum Computation
• Grover's Algorithm with Diffusion and Amplitude Steering
• Efficient Quantum Algorithms related to Autocorrelation Spectrum
• Iterative Decoding of Trellis-Constrained Codes inspired by Amplitude Amplification (Preliminary Version)