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/9810017

An Inherently Quantum Computation Paradigm: NP-complete=P Under the Hypothetical Notion of Continuous Uncomplete von Neumann Measurement

Giuseppe Castagnoli

Published Oct 6, 1998• 1 citation
arXivHTMLPDF

Abstract

The topical quantum computation paradigm is a transposition of the Turing machine into the quantum framework. Implementations based on this paradigm have limitations as to the number of: qubits, computation steps, efficient quantum algorithms (found so far). A new exclusively quantum paradigm (with no classical counterpart) is propounded, based on the speculative notion of continuous uncomplete von Neumann measurement. Under such a notion, NP-complete is equal to P. This can provide a mathematical framework for the search of implementable paradigms, possibly exploiting particle statistics.

DOI
10.48550/arxiv.quant-ph/9810017

Related papers

Exploiting Particle Statistics in Quantum Computation

Giuseppe Castagnoli, Dalida Monti

We describe a plausible-speculative form of quantum computation which exploits particle (fermionic, bosonic) statistics, under a generalized, counterfactual interpretation thereof. In the idealized situation of an isolated system, it seems that this form of computation yields to NP-complete=P.

arXiv:quant-ph/9806086•Jun 25, 1998•0 citations

Computing the Noncomputable

Tien D. Kieu

We explore in the framework of Quantum Computation the notion of computability, which holds a central position in Mathematics and Theoretical Computer Science. A quantum algorithm that exploits the quantum adiabatic which is equivalent to the Turing halting problem and known to be mathematically noncomputable. Generalised quantum algorithms are also considered for some other mathematical noncomputables in the same and of different noncomputability classes. The key element of all these algorithms is the measurability of both the values of physical observables and of the quantum-mechanical probability distributions for these values. It is argued that computability, and thus the limits of Mathematics, ought to be determined not

•Mar 7, 2002•59 citations

QUANTUM COMPUTATION: AN INTRODUCTION

Adriano Barenco

When applied to computation, quantum mechanics opens completely new perspectives; by exploiting quantum mechanical features such as entanglement or super-position, one can solve some problems much more efficiently than with classical computers. One of the most striking examples is the factoring problem. This task is believed to be out of reach of classical computers as soon as the number of digits in the number to factor exceeds a certain limit. In this contribution, we present the basic notion of quantum computation and review the most common quantum algorithms discovered so far.

WORLD SCIENTIFIC eBooks•Oct 1, 1998•13 citations

Quantum Computation and NP-Complete Problems

Tetsuro Nishino

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.

•Jul 1, 2000•0 citations

Quantum Turing Machines: Computations and Measurements

Stefano Guerrini, Simone Martini, Andrea Masini

Contrary to the classical case, the relation between quantum programming languages and quantum Turing Machines (QTM) has not been fully investigated. In particular, there are features of QTMs that have not been exploited, a notable example being the intrinsic infinite nature of any quantum computation. In this paper, we propose a definition of QTM, which extends and unifies the notions of Deutsch and Bernstein & Vazirani. In particular, we allow both arbitrary quantum input, and meaningful superpositions of computations, where some of them are “terminated” with an “output”, while others are not. For some infinite computations an “output” is obtained as a limit of finite portions of the computation. We propose a natural and robust observation protocol for our QTMs, which does not modify the probability of the possible outcomes of the machines. Finally, we use QTMs to define a class of quantum computable functions—any such function is a mapping from a general quantum state to a probability distribution of natural numbers. We expect that our class of functions, when restricted to classical input-output, will not be different from the set of the recursive functions.

arXiv:1703.07748•Applied Sciences•Aug 11, 2020•11 citations

Quantum computation

This chapter introduces the basic principles of quantum computation. We shall adhere to the quantum circuit model of computation, with which it is easy to work and which is close to physical implementations. We shall not discuss the more abstract quantum Turing machine model, which, however, has been shown to be equivalent to the circuit model. The elementary unit of quantum information and the basic building block of quantum computation is the qubit, a two-level quantum system that can be prepared, manipulated and measured in a controlled way. A quantum computer can be seen as a collection of n qubits and therefore its wave function resides in a 2 n -dimensional complex Hilbert space. As far as coupling to the environment may be neglected, its evolution in time is unitary and governed by the Schrödinger equation. A quantum computation is composed of three basic steps: preparation of the input state, implementation of the desired unitary transformation acting on this state and measurement of the output state. The output of the measurement process is inherently probabilistic and the probabilities of the different possible outputs are set by the basic postulates of quantum mechanics. Therefore, in a quantum algorithm we must, in general, repeat several times the algorithm to obtain the correct solution of our problem with probability as close to one as desired. In this sense, quantum algorithms are analogous to classical probabilistic algorithms. However, the superposition principle and quantum entanglement open up new possibilities for computation. Quantum computers are potentially more powerful than classical (deterministic or probabilistic) computers due to quantum interference and entanglement. We show that, analogously to classical computation, there exists a small set of gates that are universal, that is, any unitary transformation can be decomposed into a sequence of these gates. We then discuss the implementation of the basic Boolean functions and arithmetic operations on a quantum computer.

WORLD SCIENTIFIC eBooks•Dec 1, 2018•0 citations
The topical quantum computation paradigm is a transposition of the Turing machine into the quantum framework. Implementations based on this paradigm have limitations as to the number of: qubits, computation steps, efficient quantum algorithms (found so far). A new exclusively quantum paradigm (with no classical counterpart) is propounded, based on the speculative notion of continuous uncomplete von Neumann measurement. Under such a notion, NP-complete is equal to P. This can provide a mathematical framework for the search of implementable paradigms, possibly exploiting particle statistics.
We explore in the framework of Quantum Computation the notion of computability, which holds a central position in Mathematics and Theoretical Computer Science. A quantum algorithm that exploits the quantum adiabatic which is equivalent to the Turing halting problem and known to be mathematically noncomputable. Generalised quantum algorithms are also considered for some other mathematical noncomputables in the same and of different noncomputability classes. The key element of all these algorithms is the measurability of both the values of physical observables and of the quantum-mechanical probability distributions for these values. It is argued that computability, and thus the limits of Mathematics, ought to be determined not
When applied to computation, quantum mechanics opens completely new perspectives; by exploiting quantum mechanical features such as entanglement or super-position, one can solve some problems much more efficiently than with classical computers. One of the most striking examples is the factoring problem. This task is believed to be out of reach of classical computers as soon as the number of digits in the number to factor exceeds a certain limit. In this contribution, we present the basic notion of quantum computation and review the most common quantum algorithms discovered so far.
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.
Contrary to the classical case, the relation between quantum programming languages and quantum Turing Machines (QTM) has not been fully investigated. In particular, there are features of QTMs that have not been exploited, a notable example being the intrinsic infinite nature of any quantum computation. In this paper, we propose a definition of QTM, which extends and unifies the notions of Deutsch and Bernstein & Vazirani. In particular, we allow both arbitrary quantum input, and meaningful superpositions of computations, where some of them are “terminated” with an “output”, while others are not. For some infinite computations an “output” is obtained as a limit of finite portions of the computation. We propose a natural and robust observation protocol for our QTMs, which does not modify the probability of the possible outcomes of the machines. Finally, we use QTMs to define a class of quantum computable functions—any such function is a mapping from a general quantum state to a probability distribution of natural numbers. We expect that our class of functions, when restricted to classical input-output, will not be different from the set of the recursive functions.
This chapter introduces the basic principles of quantum computation. We shall adhere to the quantum circuit model of computation, with which it is easy to work and which is close to physical implementations. We shall not discuss the more abstract quantum Turing machine model, which, however, has been shown to be equivalent to the circuit model. The elementary unit of quantum information and the basic building block of quantum computation is the qubit, a two-level quantum system that can be prepared, manipulated and measured in a controlled way. A quantum computer can be seen as a collection of n qubits and therefore its wave function resides in a 2 n -dimensional complex Hilbert space. As far as coupling to the environment may be neglected, its evolution in time is unitary and governed by the Schrödinger equation. A quantum computation is composed of three basic steps: preparation of the input state, implementation of the desired unitary transformation acting on this state and measurement of the output state. The output of the measurement process is inherently probabilistic and the probabilities of the different possible outputs are set by the basic postulates of quantum mechanics. Therefore, in a quantum algorithm we must, in general, repeat several times the algorithm to obtain the correct solution of our problem with probability as close to one as desired. In this sense, quantum algorithms are analogous to classical probabilistic algorithms. However, the superposition principle and quantum entanglement open up new possibilities for computation. Quantum computers are potentially more powerful than classical (deterministic or probabilistic) computers due to quantum interference and entanglement. We show that, analogously to classical computation, there exists a small set of gates that are universal, that is, any unitary transformation can be decomposed into a sequence of these gates. We then discuss the implementation of the basic Boolean functions and arithmetic operations on a quantum computer.