Perfect computational equivalence between quantum Turing machines and finitely generated uniform quantum circuit families
From MaRDI portal
(Redirected from Publication:1009352)
Abstract: In order to establish the computational equivalence between quantum Turing machines (QTMs) and quantum circuit families (QCFs) using Yao's quantum circuit simulation of QTMs, we previously introduced the class of uniform QCFs based on an infinite set of elementary gates, which has been shown to be computationally equivalent to the polynomial-time QTMs (with appropriate restriction of amplitudes) up to bounded error simulation. This result implies that the complexity class BQP introduced by Bernstein and Vazirani for QTMs equals its counterpart for uniform QCFs. However, the complexity classes ZQP and EQP for QTMs do not appear to equal their counterparts for uniform QCFs. In this paper, we introduce a subclass of uniform QCFs, the finitely generated uniform QCFs, based on finite number of elementary gates and show that the class of finitely generated uniform QCFs is perfectly equivalent to the class of polynomial-time QTMs; they can exactly simulate each other. This naturally implies that BQP as well as ZQP and EQP equal the corresponding complexity classes of the finitely generated uniform QCFs.
Recommendations
- Computational complexity of uniform quantum circuit families and quantum Turing machines
- Uniformity of quantum circuit families for error-free algorithms
- Revisiting the simulation of quantum Turing machines by quantum circuits
- Universality of quantum Turing machines with deterministic control
- Classically controlled quantum computation
Cites work
- scientific article; zbMATH DE number 1579275 (Why is no real title available?)
- scientific article; zbMATH DE number 5608701 (Why is no real title available?)
- scientific article; zbMATH DE number 52121 (Why is no real title available?)
- scientific article; zbMATH DE number 610968 (Why is no real title available?)
- scientific article; zbMATH DE number 1418357 (Why is no real title available?)
- Computational complexity of real functions
- Computational complexity of uniform quantum circuit families and quantum Turing machines
- Counting, fanout and the complexity of quantum ACC
- EXACT QUANTUM FOURIER TRANSFORMS AND DISCRETE LOGARITHM ALGORITHMS
- Local transition functions of quantum Turing machines
- Log Depth Circuits for Division and Related Problems
- On Relating Time and Space to Size and Depth
- On uniform circuit complexity
- Parallelization, amplification, and exponential time simulation of quantum interactive proof systems
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- QUANTUM COMPUTATION WITH RESTRICTED AMPLITUDES
- Quantum Complexity Theory
- Quantum Computability
- Quantum complexity theory
- Quantum computational networks
- Quantum theory, the Church–Turing principle and the universal quantum computer
- Uniformity of quantum circuit families for error-free algorithms
Cited in
(9)- QPCF: higher-order languages and quantum circuits
- Zero sum subsequences and hidden subgroups
- Computational complexity of uniform quantum circuit families and quantum Turing machines
- Universality, invariance, and the foundations of computational complexity in the light of the quantum computer
- Uniformity of quantum circuit families for error-free algorithms
- Quantum implicit computational complexity
- Revisiting the simulation of quantum Turing machines by quantum circuits
- A branching distributed temporal logic for reasoning about entanglement-free quantum state transformations
- \textsc{qPCF}: a language for quantum circuit computations
This page was built for publication: Perfect computational equivalence between quantum Turing machines and finitely generated uniform quantum circuit families
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1009352)
