Perfect computational equivalence between quantum Turing machines and finitely generated uniform quantum circuit families

DOI10.1007/S11128-008-0091-8zbMATH Open1200.81029arXivquant-ph/0511117OpenAlexW3099196844MaRDI QIDQ1009352FDOQ1009352

Harumichi Nishimura, Masanao Ozawa

Publication date: 31 March 2009

Published in: Quantum Information Processing (Search for Journal in Brave)

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.

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

zbMATH Keywords

Complexity theoryTuring machinesQuantum computationFinitely generated uniform quantum circuit familiesUniform circuit families

Mathematics Subject Classification ID

Quantum computation (81P68) Analytic circuit theory (94C05)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Quantum theory, the Church–Turing principle and the universal quantum computer
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Quantum Computability
• On uniform circuit complexity
• Quantum computational networks
• Parallelization, amplification, and exponential time simulation of quantum interactive proof systems
• Quantum Complexity Theory
• Quantum complexity theory
• On Relating Time and Space to Size and Depth
• EXACT QUANTUM FOURIER TRANSFORMS AND DISCRETE LOGARITHM ALGORITHMS
• Log Depth Circuits for Division and Related Problems
• Computational complexity of real functions
• Computational complexity of uniform quantum circuit families and quantum Turing machines
• Uniformity of quantum circuit families for error-free algorithms
• Local transition functions of quantum Turing machines
• QUANTUM COMPUTATION WITH RESTRICTED AMPLITUDES

Cited In (7)

• QPCF: higher-order languages and quantum circuits
• Universality, Invariance, and the Foundations of Computational Complexity in the Light of the Quantum Computer
• $$\mathsf {qPCF}$$ : A Language for Quantum Circuit Computations
• Zero sum subsequences and hidden subgroups
• Uniformity of quantum circuit families for error-free algorithms
• Quantum implicit computational complexity
• A branching distributed temporal logic for reasoning about entanglement-free quantum state transformations

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)