Quantum Computability
From MaRDI portal
Publication:4376180
DOI10.1137/S0097539795293639zbMath0895.68043OpenAlexW2913788899MaRDI QIDQ4376180
Jonathan DeMarrais, Leonard M. Adleman, Ming-Deh A. Huang
Publication date: 10 February 1998
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539795293639
Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Foundations, quantum information and its processing, quantum axioms, and philosophy (81P99) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Improving direct state measurements by using rebits in real enlarged Hilbert spaces, Quantum information distance, Unnamed Item, A new universal and fault-tolerant quantum basis, Complexity Bounds of Constant-Space Quantum Computation, Polynomial time quantum computation with advice, Quantum simulation from the bottom up: the case of rebits, Nondeterministic unitary OBDDs, Uncountable realtime probabilistic classes, Unnamed Item, Quantum Finite Automata: A Modern Introduction, Entropy and algorithmic complexity in quantum information theory, Interference as a computational resource: a tutorial, Complexity limitations on quantum computation, Circuit Lower Bounds for Nondeterministic Quasi-polytime from a New Easy Witness Lemma, A structured view on weighted counting with relations to counting, quantum computation and applications, Classical Ising model test for quantum circuits, ANALYSIS OF QUANTUM FUNCTIONS, QUANTUM COMPUTATION WITH RESTRICTED AMPLITUDES, Entropy and quantum Kolmogorov complexity: a quantum Brudno's theorem, Revisiting the simulation of quantum Turing machines by quantum circuits, Quantum Algorithmic Complexities and Entropy, Quantum and classical complexity classes: Separations, collapses, and closure properties, Uniformity of quantum circuit families for error-free algorithms, Quantum branching programs and space-bounded nonuniform quantum complexity, EXACT NON-IDENTITY CHECK IS NQP-COMPLETE, Debates with Small Transparent Quantum Verifiers, Determining the equivalence for one-way quantum finite automata, A new connection between quantum circuits, graphs and the Ising partition function, Quantum algorithms for algebraic problems, Perfect computational equivalence between quantum Turing machines and finitely generated uniform quantum circuit families, Quantum zero-error algorithms cannot be composed, Unnamed Item, Uncountable classical and quantum complexity classes, Languages Recognized with Unbounded Error by Quantum Finite Automata, $$P\mathop{ =}\limits^{?}NP$$, Theory of one-tape linear-time Turing machines, Quantum random access stored-program machines, A common algebraic description for probabilistic and quantum computations, A SCHEMATIC DEFINITION OF QUANTUM POLYNOMIAL TIME COMPUTABILITY, Quantum computing and quadratically signed weight enumerators, Computational complexity of uniform quantum circuit families and quantum Turing machines, Classical simulation of quantum circuits by half Gauss sums, Computation with multiple CTCs of fixed length and width, PSPACE has constant-round quantum interactive proof systems, One complexity theorist's view of quantum computing
