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 computationcomplexity theoryquantum Turing machinesuniform quantum circuit familiesuniversal quantum Turing machines

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Quantum computation (81P68)

Related Items (18)

Polynomial time quantum computation with advice ⋮ Zero sum subsequences and hidden subgroups ⋮ On quantum lambda calculi: a foundational perspective ⋮ Implementation of an E-payment security evaluation system based on quantum blind computing ⋮ THE SECOND QUANTIZED QUANTUM TURING MACHINE AND KOLMOGOROV COMPLEXITY ⋮ Power of uninitialized qubits in shallow quantum circuits ⋮ ANALYSIS OF QUANTUM FUNCTIONS ⋮ Classically simulating quantum circuits with local depolarizing noise ⋮ Hilbert’s sixth problem: the endless road to rigour ⋮ Models of quantum computation and quantum programming languages ⋮ Uniformity of quantum circuit families for error-free algorithms ⋮ Quantum branching programs and space-bounded nonuniform quantum complexity ⋮ Unnamed Item ⋮ Perfect computational equivalence between quantum Turing machines and finitely generated uniform quantum circuit families ⋮ On a measurement-free quantum lambda calculus with classical control ⋮ Quantum implicit computational complexity ⋮ Quantum random access stored-program machines ⋮ A SCHEMATIC DEFINITION OF QUANTUM POLYNOMIAL TIME COMPUTABILITY

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

This page was built for publication: Computational complexity of uniform quantum circuit families and quantum Turing machines