Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:quant-ph/9906095 · Theoretical Computer Science

Computational complexity of uniform quantum circuit families and quantum Turing machines Communicated by O. Watanabe

Harumichi Nishimura, Masanao Ozawa

Published Apr 1, 2002• 71 citations
arXivHTMLPDF
DOI
10.1016/s0304-3975(01)00111-6

Related papers

Computational Complexity Theory of Quantum Turing Machines and Quantum Circuits

Harumichi Nishimura, 治道 西村

•Mar 26, 2001•1 citation

Perfect Computational Equivalence between Quantum Turing Machines and Finitely Generated Uniform Quantum Circuit Families

Harumichi Nishimura, Masanao Ozawa

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 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 equal their counterparts 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, finitely generated uniform QCFs, based on finite number of elementary gates and show that the finitely generated uniform QCF is perfectly equivalent to the polynomial-time QTM; 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 QCF.

•Nov 12, 2005•27 citations

The Complexity of Quantum Computation(量子計算の複雑さに関する研究)

孝志 三原

•Jan 1, 1997•0 citations

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

Harumichi Nishimura, Masanao Ozawa

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.

arXiv:quant-ph/0511117•Quantum Information Processing•Jan 15, 2009•21 citations

Revisiting the simulation of quantum Turing machines by quantum circuits

Abel Molina, John Watrous

Yao's 1995 publication ‘Quantum circuit complexity’ in Proceedings of the 34th Annual IEEE Symposium on Foundations of Computer Science , pp. 352–361, proved that quantum Turing machines and quantum circuits are polynomially equivalent computational models: t ≥ n steps of a quantum Turing machine running on an input of length n can be simulated by a uniformly generated family of quantum circuits with size quadratic in t , and a polynomial-time uniformly generated family of quantum circuits can be simulated by a quantum Turing machine running in polynomial time. We revisit the simulation of quantum Turing machines with uniformly generated quantum circuits, which is the more challenging of the two simulation tasks, and present a variation on the simulation method employed by Yao together with an analysis of it. This analysis reveals that the simulation of quantum Turing machines can be performed by quantum circuits having depth linear in t , rather than quadratic depth, and can be extended to variants of quantum Turing machines, such as ones having multi-dimensional tapes. Our analysis is based on an extension of method described by Arright, Nesme and Werner in 2011 in Journal of Computer and System Sciences 77 , 372–378. ( doi:10.1016/j.jcss.2010.05.004 ), that allows for the localization of causal unitary evolutions.

arXiv:1808.01701•Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences•Jun 1, 2019•65 citations

A formulation of Quantum Turing Machine

Ryuichi Sawae, Hiroshi Takeuchi, Tadahito Harima

•Dec 1, 1995•0 citations
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 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 equal their counterparts 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, finitely generated uniform QCFs, based on finite number of elementary gates and show that the finitely generated uniform QCF is perfectly equivalent to the polynomial-time QTM; 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 QCF.
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.
Yao's 1995 publication ‘Quantum circuit complexity’ in Proceedings of the 34th Annual IEEE Symposium on Foundations of Computer Science , pp. 352–361, proved that quantum Turing machines and quantum circuits are polynomially equivalent computational models: t ≥ n steps of a quantum Turing machine running on an input of length n can be simulated by a uniformly generated family of quantum circuits with size quadratic in t , and a polynomial-time uniformly generated family of quantum circuits can be simulated by a quantum Turing machine running in polynomial time. We revisit the simulation of quantum Turing machines with uniformly generated quantum circuits, which is the more challenging of the two simulation tasks, and present a variation on the simulation method employed by Yao together with an analysis of it. This analysis reveals that the simulation of quantum Turing machines can be performed by quantum circuits having depth linear in t , rather than quadratic depth, and can be extended to variants of quantum Turing machines, such as ones having multi-dimensional tapes. Our analysis is based on an extension of method described by Arright, Nesme and Werner in 2011 in Journal of Computer and System Sciences 77 , 372–378. ( doi:10.1016/j.jcss.2010.05.004 ), that allows for the localization of causal unitary evolutions.