Computational Complexity Theory of Quantum Turing Machines and Quantum Circuits

Harumichi Nishimura, Masanao Ozawa

Deutsch proposed two sorts of models of quantum computers, quantum Turing machines (QTMs) and quantum circuit families (QCFs). In this paper we explore the computational powers of these models and re-examine the claim of the computational equivalence of these models often made in the literature without detailed investigations. For this purpose, we formulate the notion of the codes of QCFs and the uniformity of QCFs by the computability of the codes. Various complexity classes are introduced for QTMs and QCFs according to constraints on the error probability of algorithms or transition amplitudes. Their interrelations are examined in detail. For Monte Carlo algorithms, it is proved that the complexity classes based on uniform QCFs are identical with the corresponding classes based on QTMs. However, for Las Vegas algorithms, it is still open whether the two models are equivalent. We indicate the possibility that they are not equivalent. In addition, we give a complete proof of the existence of a universal QTM simulating multi-tape QTMs efficiently. We also examine the simulation of various types of QTMs such as multi-tape QTMs, single tape QTMs, stationary, normal form QTMs (SNQTMs), and QTMs with the binary tapes. As a result, we show that these QTMs are computationally equivalent one another as computing models implementing not only Monte Carlo algorithms but exact (or error-free) ones.

R. Hayakawa, Tomoyuki Morimae

考志 三原

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.

Lance Fortnow

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.