Quantum complexity theory

DOI10.1145/167088.167097zbMath1310.68080OpenAlexW1993688167WikidataQ56813578 ScholiaQ56813578MaRDI QIDQ5248467

Publication date: 7 May 2015

Published in: Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/167088.167097

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Quantum algorithms and complexity in the theory of computing (68Q12)

Related Items

Efficient quantum algorithms of finding the roots of a polynomial function, Quantum entanglement as a new information processing resource, Unnamed Item, Circuit complexity in interacting QFTs and RG flows, Quantum computation with coherent spin states and the close Hadamard problem, Efficient computation of permanents, with applications to boson sampling and random matrices, Creating very true quantum algorithms for quantum energy based computing, Testing the shift-equivalence of polynomials using quantum machines, Analytical error analysis of Clifford gates by the fault-path tracer method, Quantum differential and linear cryptanalysis, Kochen-Specker theorem as a precondition for quantum computing, Monoidal computer. I: Basic computability by string diagrams, Testing shift-equivalence of polynomials by deterministic, probabilistic and quantum machines., Quantum learning Boolean linear functions w.r.t. product distributions, Distributed Bernstein-Vazirani algorithm, Channel divergences and complexity in algebraic QFT, Time evolution of complexity: a critique of three methods, A user-centric quantum benchmarking test suite and evaluation framework, Commuting quantum circuits and complexity of Ising partition functions, A generalization of Bernstein-Vazirani algorithm with multiple secret keys and a probabilistic oracle, Application of quantum approximate optimization algorithm to job shop scheduling problem, Quaternionic quantum automata, On the simulation of quantum Turing machines., Quantum algorithms for the Goldreich-Levin learning problem, A quantum algorithm to approximate the linear structures of Boolean functions, QCB: efficient quantum-secure authenticated encryption, Generalization of Deutsch's algorithm, Computational complexity and applications of quantum algorithm, A classical probability space exists for the measurement theory based on the truth values, Unnamed Item, New quantum algorithm for studying NP-complete problems, The quadratic speedup in Grover's search algorithm from the entanglement perspective, The Road to Quantum Computational Supremacy, Necessary and sufficient condition for quantum computing, Quantum communication based on an algorithm of determining a matrix, Reversible simulation of space-bounded computations, A quantum algorithm for a FULL adder operation based on registers of the CPU in a quantum-gated computer, Local random quantum circuits are approximate polynomial-designs, Physics' evolution toward computing, Revisiting the simulation of quantum Turing machines by quantum circuits, Quantum finite automata: advances on Bertoni's ideas, New quantum algorithm solving the NP complete problem, Computational universes, Quantum algorithm for determining a complex number string, Counting by quantum eigenvalue estimation, Quantum loop programs, The geometry of quantum learning, New method of calculating a multiplication by using the generalized Bernstein-Vazirani algorithm, Monoidal computer III: a coalgebraic view of computability and complexity (extended abstract), Perfect computational equivalence between quantum Turing machines and finitely generated uniform quantum circuit families, Some theoretically organized algorithm for quantum computers, Quantum search on structured problems, Recursive information transducers: Computation models, Stochastic analog networks and computational complexity, Quantum algorithm for the root-finding problem, Necessary and Sufficient Conditions for Quantum Computation, Oracle Quantum Computing, Quantum computation based on retarded and advanced propagation., A framework for structured quantum search., Quantum model of computations: Underlying principles and achievements, On the impossibility of interaction-free quantum sensing for small I/O bandwidth, Regular languages accepted by quantum automata, Improved BV-based quantum attack on block ciphers, Computational complexity of uniform quantum circuit families and quantum Turing machines, A quantum algorithm for approximating the influences of Boolean functions and its applications, Quantum mechanics and computation