Quantum Complexity Theory

DOI10.1137/S0097539796300921zbMath0895.68042DBLPjournals/siamcomp/BernsteinV97WikidataQ55878430 ScholiaQ55878430MaRDI QIDQ4376183

Ethan Bernstein, Umesh V. Vazirani

Publication date: 10 February 1998

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

quantum computationreversibilityquantum Turing machinesFourier samplingquantum polynomial timeuniversal quantum Turing machine

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Turing machines and related notions (03D10)

Related Items (only showing first 100 items - show all)

Quantum information distance ⋮ Generality's price: Inescapable deficiencies in machine-learned programs ⋮ A public key cryptosystem based on data complexity under quantum environment ⋮ Search by Quantum Walks on Two-Dimensional Grid without Amplitude Amplification ⋮ Quantum Algorithms to Solve the Hidden Shift Problem for Quadratics and for Functions of Large Gowers Norm ⋮ The Sturm-Liouville eigenvalue problem and NP-complete problems in the quantum setting with queries ⋮ Quantum machine learning: a classical perspective ⋮ Quantum algorithm for multivariate polynomial interpolation ⋮ Polynomial time quantum computation with advice ⋮ Quantum simulation from the bottom up: the case of rebits ⋮ Kochen-Specker theorem as a precondition for quantum computing ⋮ Nondeterministic finite automata based on quantum logic: language equivalence relation and robustness ⋮ Scalable programmable quantum gates and a new aspect of the additivity problem for the classical capacity of quantum channels ⋮ Efficient discrete approximations of quantum gates ⋮ Undecidability of the Spectral Gap ⋮ Quantum image processing? ⋮ “Quantumness” versus “classicality” of quantum states and quantum protocols ⋮ Using Bernstein-Vazirani algorithm to attack block ciphers ⋮ A modeling and verification framework for optical quantum circuits ⋮ An exact quantum algorithm for a restricted subtraction game ⋮ Rapid solution of problems by quantum computation ⋮ An exact quantum algorithm for testing Boolean functions with one uncomplemented product of two variables ⋮ A quantum related-key attack based on the Bernstein-Vazirani algorithm ⋮ Quantum algorithms for learning the algebraic normal form of quadratic Boolean functions ⋮ Sample-size-reduction of quantum states for the noisy linear problem ⋮ An exact quantum algorithm for testing 3-junta in Boolean functions with one uncomplemented product ⋮ A quantum distinguisher for 7/8-round SMS4 block cipher ⋮ Quantum key-recovery attack on Feistel constructions: Bernstein-Vazirani meet Grover algorithm ⋮ The complexity of translationally invariant low-dimensional spin lattices in 3D ⋮ Generalization of Deutsch's algorithm ⋮ Quantum forgery attacks on COPA, AES-COPA and marble authenticated encryption algorithms ⋮ Unnamed Item ⋮ On a poset of quantum exact promise problems ⋮ A generalisation of the phase kick-back ⋮ Quantum circuits and low-degree polynomials over ${{\mathbb{F}}_\mathsf{2}}$ ⋮ On quantum lambda calculi: a foundational perspective ⋮ Unnamed Item ⋮ Histogram-based segmentation of quantum images ⋮ THE SECOND QUANTIZED QUANTUM TURING MACHINE AND KOLMOGOROV COMPLEXITY ⋮ A structured view on weighted counting with relations to counting, quantum computation and applications ⋮ A LOGIC FOR QUANTUM COMPUTATION AND CLASSICAL SIMULATION OF QUANTUM ALGORITHMS ⋮ SECOND QUANTIZED KOLMOGOROV COMPLEXITY ⋮ Entanglement consumption of instantaneous nonlocal quantum measurements ⋮ Local Transition Functions of Quantum Turing Machines ⋮ An Introduction to Quantum Computing, without the Physics ⋮ Automata theory based on quantum logic: reversibilities and pushdown automata ⋮ Entropy and quantum Kolmogorov complexity: a quantum Brudno's theorem ⋮ Can a Quantum Computer Run the von Neumann Architecture? ⋮ Quantum algorithms for learning and testing juntas ⋮ An introduction to quantum annealing ⋮ Realizable Hamiltonians for universal adiabatic quantum computers ⋮ On the complexity of the multivariate Sturm-Liouville eigenvalue problem ⋮ A quantum algorithm for a FULL adder operation based on registers of the CPU in a quantum-gated computer ⋮ Physics' evolution toward computing ⋮ An exact quantum algorithm for the 2-junta problem ⋮ Modular quantum computing and quantum-like devices ⋮ NMR Quantum Computing ⋮ Quantum Algorithmic Complexities and Entropy ⋮ Models of quantum computation and quantum programming languages ⋮ Measurement-Based and Universal Blind Quantum Computation ⋮ Computing spin networks ⋮ Quantum and classical complexity classes: Separations, collapses, and closure properties ⋮ Some formal tools for analyzing quantum automata. ⋮ Improved bounds on quantum learning algorithms ⋮ Approximation and robustness of fuzzy finite automata ⋮ Hierarchy and equivalence of multi-letter quantum finite automata ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Zeno machines and hypercomputation ⋮ Determination of equivalence between quantum sequential machines ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Quantum principles and mathematical computability ⋮ Error-bounded probabilistic computations between MA and AM ⋮ On Halting Process of Quantum Turing Machine ⋮ Determining the equivalence for one-way quantum finite automata ⋮ Universality and programmability of quantum computers ⋮ Quantum matchgate computations and linear threshold gates ⋮ Quantum algorithms for algebraic problems ⋮ Quantum computation and quantum information† ⋮ On a measurement-free quantum lambda calculus with classical control ⋮ Some theoretically organized algorithm for quantum computers ⋮ Universality, Invariance, and the Foundations of Computational Complexity in the Light of the Quantum Computer ⋮ DELETING A MARKED BASIS-STATE FROM AN EVEN SUPERPOSITION OF ALL BASIS-STATES WITH A SINGLE QUERY ⋮ ON THE QUANTUM KOLMOGOROV COMPLEXITY OF CLASSICAL STRINGS ⋮ On Quantum Chosen-Ciphertext Attacks and Learning with Errors ⋮ Identifying Generalized Reed-Muller Codewords by Quantum Queries ⋮ Languages Recognized with Unbounded Error by Quantum Finite Automata ⋮ Partial Observation of Quantum Turing Machines and a Weaker Well-Formedness Condition ⋮ Verification of quantum computation: an overview of existing approaches ⋮ SOME REMARKS ON QUANTUM AUTOMATA ⋮ Fiber-Optics Implementation of the Deutsch-Jozsa and Bernstein-Vazirani Quantum Algorithms with Three Qubits ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Quantum Hardness of Learning Shallow Classical Circuits ⋮ Quantum algorithm for the root-finding problem ⋮ The quantum ultimatum game ⋮ Quantum computing: beyond the limits of conventional computation† ⋮ On exact quantum query complexity ⋮ Quantum algorithms for learning symmetric juntas via the adversary bound

This page was built for publication: Quantum Complexity Theory