Computational complexity of uniform quantum circuit families and quantum Turing machines

DOI10.1016/S0304-3975(01)00111-6zbMath1002.68055arXivquant-ph/9906095MaRDI QIDQ1605308

Harumichi Nishimura, Masanao Ozawa

Publication date: 15 July 2002

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/quant-ph/9906095

zbMATH Keywords

quantum computation; complexity theory; quantum Turing machines; uniform quantum circuit families; universal quantum Turing machines

Mathematics Subject Classification ID

68Q10: Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)

81P68: Quantum computation

Related Items

ANALYSIS OF QUANTUM FUNCTIONS, Perfect computational equivalence between quantum Turing machines and finitely generated uniform quantum circuit families, Quantum implicit computational complexity, Uniformity of quantum circuit families for error-free algorithms, Quantum branching programs and space-bounded nonuniform quantum complexity, Models of quantum computation and quantum programming languages, Polynomial time quantum computation with advice, On quantum lambda calculi: a foundational perspective, THE SECOND QUANTIZED QUANTUM TURING MACHINE AND KOLMOGOROV COMPLEXITY, On a measurement-free quantum lambda calculus with classical control

Cites Work

• Unnamed Item
• Unnamed Item
• Computational complexity of real functions
• Primality testing and Abelian varieties over finite fields
• The computer as a physical system: a microscopic quantum mechanical Hamiltonian model of computers as represented by Turing machines
• Quantum computational networks
• Rapid solution of problems by quantum computation
• A Fast Monte-Carlo Test for Primality
• Quantum theory, the Church–Turing principle and the universal quantum computer
• Quantum computations: algorithms and error correction
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Quantum Computability
• Quantum Complexity Theory
• Strengths and Weaknesses of Quantum Computing
• Oracle Quantum Computing
• Quantum complexity theory
• Logical Reversibility of Computation