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

Quantum Computation and NP-Complete Problems

Tetsuro Nishino

Published Jul 1, 2000• 0 citations
Publisher

Abstract

In this paper, we show the following two results on the relationships between quantum computers and NP-complete problems. First, we develop a theory of bulk quantum computation such as NMR (Nuclear Magnetic Resonance) quantum computation. For this purpose, we first define bulk quantum Turing machine (BQTM for short) as a model of bulk quantum computation. Then, we show that BQTMs can solve certain instances of NP-complete problems efficiently. Next, we show that the algorithm designed by Abrams and Lloyd can be simulated by a deterministic Turing machine in polynomial space. This suggests that their algorithm, which is based on non-standard quantum mechanics, can be simulated by a standard QTM with exponential time slow down.

DOI
10.1142/9789812792761_0009

Related papers

REVIEW ON QUANTUM CHAOS ALGORITHM AND GENERALIZED QUANTUM TURING MACHINE

Satoshi Iriyama, Makoto Ohya

We have studied the quantum algorithm for several years to solve NP complete problem in polynomial times. Moreover we have discussed a computational complexity of it in terms of Turing machine. In this paper, we review some of our results and explain some new Turing machine and its language classes following our recent works 1,2 .

Quantum Bio-Informatics•Mar 1, 2008•3 citations

De computatione quantica

Gilles Brassard, José M. Fernandez

This thesis covers the topic of Quantum Computation, in both its theoretical and experimental aspects. The Theory of Quantum Computing is an extension of the standard Theory of Computation inspired by the principles of Quantum Mechanics. The discovery of efficient quantum algorithms for problems for which no efficient classical algorithms are known challenges the Strong Church-Turing Thesis, which states that all computational models are essentially equivalent in terms of what they can compute and how efficiently they can do so. In Part I of this thesis, we study the nature of this difference. We first introduce a general and simplified framework for characterising the essence of a quantum theory, in contrast with a deterministic or a probabilistic theory. We put forth the thesis that the most fundamental axioms are those related to measurement, from which these differences emanate. We cover some variations on these theories, and show some interesting structural relationships between them. For example, the only models which can be simultaneously quantum and probabilistic are the deterministic ones. We then use this meta-model to re-introduce in a succinct and uniform manner the deterministic, probabilistic and quantum versions of the Turing Machine and circuit computational models. Moreover, we generalise the circuit model on arbitrary semirings. We thus succeed in providing a new classification of existing complexity classes by varying the semirings and vector norms with which their vector space of states is defined. In particular, the standard models of deterministic, probabilistic, and quantum computing can be characterised (with the same norm) by defining circuits on the boolean algebra, the positive rational or reals, and the rational or reals, respectively. We further explore this model with other non-standard semirings. We show that quaternion based models are equivalent to quantum computation. Finally, we strengthen this “algebraic hierarchy” by using the tensor formula formalism to construct a family of complete (or promise complete) problems for the corresponding complexity classes. Part II concerns experimental Quantum Computing by Nuclear Magnetic Resonance (NMR). An important obstacle in this approach is the inability to properly initialise the quantum register, which is related to the signal-to-noise problem in NMR spectroscopy. One of the most promising techniques to solve it is Algorithmic Cooling, a generalisation of the polarisation transfer techniques already used by NMR spectroscopists. We discuss the traditional adiabatic approaches and their limitations. We describe a variation on this technique, the non-adiabatic approach, which uses the environment in order to cool beyond these limits. In particular, we provide a new, efficient non-adiabatic cooling algorithm which could achieve near-zero spin temperatures in liquid-state NMR already with more reasonably sized registers (30–60 spins). Finally, we report on the successful laboratory realisation of the first ever non-adiabatic cooling experiment. This constitutes, we hope, the first step towards the fully fledged development of this promising technique, with applications far beyond NMR-based Quantum Computing.

•Jan 1, 2004•7 citations

A Note on Bulk Quantum Turing Machine

Tetsushi Matsui

Recently, among experiments for realization of quantum computers, NMR quantum computers have achieved the most impressive succession. There is a model of the NMR quantum computation,namely Atsumi and Nishino's bulk quantum Turing Machine. It assumes, however, an unnatural assumption with quantum mechanics. We, then, define a more natural and quantum mechanically realizable modified bulk quantum Turing Machine, and show its computational ability by comparing complexity classes with quantum Turing Machine's counter part.

arXiv:cs/0411037•Nov 12, 2004•2 citations

Quantum Complexity Theory

Ethan Bernstein, Umesh V. Vazirani

In this paper we study quantum computation from a complexity theoretic viewpoint. Our first result is the existence of an efficient universal quantum Turing machine in Deutsch's model of a quantum Turing machine (QTM) [Proc. Roy. Soc. London Ser. A, 400 (1985), pp. 97--117]. This construction is substantially more complicated than the corresponding construction for classical Turing machines (TMs); in fact, even simple primitives such as looping, branching, and composition are not straightforward in the context of quantum Turing machines. We establish how these familiar primitives can be implemented and introduce some new, purely quantum mechanical primitives, such as changing the computational basis and carrying out an arbitrary unitary transformation of polynomially bounded dimension. We also consider the precision to which the transition amplitudes of a quantum Turing machine need to be specified. We prove that $O(\log T)$ bits of precision suffice to support a T step computation. This justifies the claim that the quantum Turing machine model should be regarded as a discrete model of computation and not an analog one. We give the first formal evidence that quantum Turing machines violate the modern (complexity theoretic) formulation of the Church--Turing thesis. We show the existence of a problem, relative to an oracle, that can be solved in polynomial time on a quantum Turing machine, but requires superpolynomial time on a bounded-error probabilistic Turing machine, and thus not in the class $\BPP$. The class $\BQP$ of languages that are efficiently decidable (with small error-probability) on a quantum Turing machine satisfies $\BPP \subseteq \BQP \subseteq \Ptime^{\SP}$. Therefore, there is no possibility of giving a mathematical proof that quantum Turing machines are more powerful than classical probabilistic Turing machines (in the unrelativized setting) unless there is a major breakthrough in complexity theory.

SIAM Journal on Computing•Oct 1, 1997•1,635 citations

量子計算と量子アルゴリズム

哲朗 西野

In 1985, David Deutsch introduced quantum Turing machines (QTMs for short) as Turing machines which can perform so called quantum parallel computations. Algorithms executed on QTMs are called quantum algorithms. It is well known that Peter Shor designed a polynomial time quantum algorithm for integer factoring in 1994. In this paper, we first illustrate several major methods of designing efficient quantum algorithms with Shor's algorithm as an example. On the other hand, many researchers are studying how to physically implement quantum computers based on QTM. Among others, NMR (Nuclear Magnetic Resonance) offers an appealing prospect for implementation of quantum computers because of a number of reasons. But, quantum computations performed on NMR is slightly different from those performed on QTMs. For example, Shor's factoring algorithm cannot be executed on an NMR quantum computer as it is. In this paper, we show how to factor integers in polynomial time by using NMR quantum computers.

•Jul 31, 2003•0 citations

Computational Power of the Quantum Turing Automata

Sina Jafarpour, Mohammad Ghodsi, Keyvan Sadri +1 more

Lots of efforts in the last decades have been done to prove or disprove whether the set of polynomially bounded problems is equal to the set of polynomially verifiable problems. This paper will present an overview of the current beliefs of quantum complexity theorists and discussion detail the impacts these beliefs may have on the future of the field. We introduce a new form of Turing machine based on the concepts of quantum mechanics and investigate the domain of this novel definition for computation. The main object is to show the domain of these computation machines and the new definition of algorithms using these automata. In section one we give a brief fundamental overview of classical complexity theory, Turing machine and all the fundamental concepts required for the next chapters. In section two we describe various classes of classical complexity automata. In next chapter we introduce quantum complexity featuring quantum Turing machines and discuss its relationship to classical complexity. Section four presents a relationship between quantum complexity classes based on the quantum Turing machines and quantum oracles, and their relationship with corresponding classical complexity classes. And section five presents a discussion on the practical phenomena in problem solving using quantum computers. Finally in section five we speculate briefly on the direction we believe the field to be headed, and what might reasonably be expected in the future

•Apr 1, 2007•0 citations
In this paper, we show the following two results on the relationships between quantum computers and NP-complete problems. First, we develop a theory of bulk quantum computation such as NMR (Nuclear Magnetic Resonance) quantum computation. For this purpose, we first define bulk quantum Turing machine (BQTM for short) as a model of bulk quantum computation. Then, we show that BQTMs can solve certain instances of NP-complete problems efficiently. Next, we show that the algorithm designed by Abrams and Lloyd can be simulated by a deterministic Turing machine in polynomial space. This suggests that their algorithm, which is based on non-standard quantum mechanics, can be simulated by a standard QTM with exponential time slow down.
This thesis covers the topic of Quantum Computation, in both its theoretical and experimental aspects. The Theory of Quantum Computing is an extension of the standard Theory of Computation inspired by the principles of Quantum Mechanics. The discovery of efficient quantum algorithms for problems for which no efficient classical algorithms are known challenges the Strong Church-Turing Thesis, which states that all computational models are essentially equivalent in terms of what they can compute and how efficiently they can do so. In Part I of this thesis, we study the nature of this difference. We first introduce a general and simplified framework for characterising the essence of a quantum theory, in contrast with a deterministic or a probabilistic theory. We put forth the thesis that the most fundamental axioms are those related to measurement, from which these differences emanate. We cover some variations on these theories, and show some interesting structural relationships between them. For example, the only models which can be simultaneously quantum and probabilistic are the deterministic ones. We then use this meta-model to re-introduce in a succinct and uniform manner the deterministic, probabilistic and quantum versions of the Turing Machine and circuit computational models. Moreover, we generalise the circuit model on arbitrary semirings. We thus succeed in providing a new classification of existing complexity classes by varying the semirings and vector norms with which their vector space of states is defined. In particular, the standard models of deterministic, probabilistic, and quantum computing can be characterised (with the same norm) by defining circuits on the boolean algebra, the positive rational or reals, and the rational or reals, respectively. We further explore this model with other non-standard semirings. We show that quaternion based models are equivalent to quantum computation. Finally, we strengthen this “algebraic hierarchy” by using the tensor formula formalism to construct a family of complete (or promise complete) problems for the corresponding complexity classes. Part II concerns experimental Quantum Computing by Nuclear Magnetic Resonance (NMR). An important obstacle in this approach is the inability to properly initialise the quantum register, which is related to the signal-to-noise problem in NMR spectroscopy. One of the most promising techniques to solve it is Algorithmic Cooling, a generalisation of the polarisation transfer techniques already used by NMR spectroscopists. We discuss the traditional adiabatic approaches and their limitations. We describe a variation on this technique, the non-adiabatic approach, which uses the environment in order to cool beyond these limits. In particular, we provide a new, efficient non-adiabatic cooling algorithm which could achieve near-zero spin temperatures in liquid-state NMR already with more reasonably sized registers (30–60 spins). Finally, we report on the successful laboratory realisation of the first ever non-adiabatic cooling experiment. This constitutes, we hope, the first step towards the fully fledged development of this promising technique, with applications far beyond NMR-based Quantum Computing.
Recently, among experiments for realization of quantum computers, NMR quantum computers have achieved the most impressive succession. There is a model of the NMR quantum computation,namely Atsumi and Nishino's bulk quantum Turing Machine. It assumes, however, an unnatural assumption with quantum mechanics. We, then, define a more natural and quantum mechanically realizable modified bulk quantum Turing Machine, and show its computational ability by comparing complexity classes with quantum Turing Machine's counter part.
In this paper we study quantum computation from a complexity theoretic viewpoint. Our first result is the existence of an efficient universal quantum Turing machine in Deutsch's model of a quantum Turing machine (QTM) [Proc. Roy. Soc. London Ser. A, 400 (1985), pp. 97--117]. This construction is substantially more complicated than the corresponding construction for classical Turing machines (TMs); in fact, even simple primitives such as looping, branching, and composition are not straightforward in the context of quantum Turing machines. We establish how these familiar primitives can be implemented and introduce some new, purely quantum mechanical primitives, such as changing the computational basis and carrying out an arbitrary unitary transformation of polynomially bounded dimension. We also consider the precision to which the transition amplitudes of a quantum Turing machine need to be specified. We prove that O(log⁡T)O(\log T)O(logT) bits of precision suffice to support a T step computation. This justifies the claim that the quantum Turing machine model should be regarded as a discrete model of computation and not an analog one. We give the first formal evidence that quantum Turing machines violate the modern (complexity theoretic) formulation of the Church--Turing thesis. We show the existence of a problem, relative to an oracle, that can be solved in polynomial time on a quantum Turing machine, but requires superpolynomial time on a bounded-error probabilistic Turing machine, and thus not in the class $\BPP$. The class $\BQP$ of languages that are efficiently decidable (with small error-probability) on a quantum Turing machine satisfies $\BPP \subseteq \BQP \subseteq \Ptime^{\SP}$. Therefore, there is no possibility of giving a mathematical proof that quantum Turing machines are more powerful than classical probabilistic Turing machines (in the unrelativized setting) unless there is a major breakthrough in complexity theory.
In 1985, David Deutsch introduced quantum Turing machines (QTMs for short) as Turing machines which can perform so called quantum parallel computations. Algorithms executed on QTMs are called quantum algorithms. It is well known that Peter Shor designed a polynomial time quantum algorithm for integer factoring in 1994. In this paper, we first illustrate several major methods of designing efficient quantum algorithms with Shor's algorithm as an example. On the other hand, many researchers are studying how to physically implement quantum computers based on QTM. Among others, NMR (Nuclear Magnetic Resonance) offers an appealing prospect for implementation of quantum computers because of a number of reasons. But, quantum computations performed on NMR is slightly different from those performed on QTMs. For example, Shor's factoring algorithm cannot be executed on an NMR quantum computer as it is. In this paper, we show how to factor integers in polynomial time by using NMR quantum computers.
Lots of efforts in the last decades have been done to prove or disprove whether the set of polynomially bounded problems is equal to the set of polynomially verifiable problems. This paper will present an overview of the current beliefs of quantum complexity theorists and discussion detail the impacts these beliefs may have on the future of the field. We introduce a new form of Turing machine based on the concepts of quantum mechanics and investigate the domain of this novel definition for computation. The main object is to show the domain of these computation machines and the new definition of algorithms using these automata. In section one we give a brief fundamental overview of classical complexity theory, Turing machine and all the fundamental concepts required for the next chapters. In section two we describe various classes of classical complexity automata. In next chapter we introduce quantum complexity featuring quantum Turing machines and discuss its relationship to classical complexity. Section four presents a relationship between quantum complexity classes based on the quantum Turing machines and quantum oracles, and their relationship with corresponding classical complexity classes. And section five presents a discussion on the practical phenomena in problem solving using quantum computers. Finally in section five we speculate briefly on the direction we believe the field to be headed, and what might reasonably be expected in the future