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

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