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• 0 citations
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•55 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•9 citations

Quantum mechanical computation

James D. Brasher

The physics and the mathematics of computation are examined to provide a foundation and perspective for the investigation of the quantum mechanics of computation. Our purpose is to explore the fundamental limits and constraints imposed on computation by Nature through the laws of physics and the mathematics of computational complexity. Inasmuch as information storage and transmission are an integral part of computation, their physical bounds are considered. The computer is viewed both physically and mathematically as a dynamical system, and is depicted in terms of the basic Turing machine paradigm. Three fundamental classes of the Turing machine are defined; the deterministic, stochastic and quantum Turing machines. Hamiltonian models and physical realizations of quantum computing are described. Quantum computers can perform some tasks which have no classical analogue, but they cannot compute functions that are non-computable by classical means. Some classically intractable problems can be solved with quantum computers.

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•Mar 1, 1994•0 citations

Quantum Computing Technologies to Accelerate 6G and CONASENSE Integration Beyond 2030

Paulo Sergio Rufino Henrique, Albena Mihovska, Ramjee Prasad

This article underscores the pivotal role of quantum computing and related technologies in advancing Communication, Navigation, Sensing, and Services Integration (CONASENSE) in the 6G realm. The study provides a methodical journey through the chronological development of computing paradigms, starting from foundational computational frameworks like Turing Machines and Von Neumann's architecture, culminating in a sophisticated understanding of Quantum Turing Machines. Tracing computing's evolution from Turing Machines to Quantum Turing Machines, it acknowledges contributions from scientists like Bohr, Einstein, Feynman, and Benioff to quantum theory. The convergence of Quantum Computing and AI offers solutions to complex, NP-hard challenges, heralding a new era of optimization. This includes Quantum Computing, Quantum Algorithms, Quantum Machine Learning (QML), Quantum Communications, Quantum Sensing & Metrology, Quantum Simulation, and Quantum Imaging within the emerging CONASENSE and 6G paradigms, projecting their sustained relevance and impact beyond 2030.

International Symposium on Wireless Personal Multimedia Communications (WPMC)•Nov 19, 2023•3 citations

Computing the maximum violation of a Bell inequality is NP-complete

Josep Amengual i Batle, C. H. Raymond Ooi

The number of steps required in order to maximize a Bell inequality for arbitrary number of qubits is shown to grow exponentially with either the number of steps and the number of parties involved. The proof that the optimization of such correlation measure is a NP-problem is based on an operational perspective involving a Turing machine, which follows a general algorithm. The implications for the computability of the so called {\it nonlocality} for any number of qubits is similar to recent results involving entanglement or similar quantum correlation-based measures.

arXiv:1503.00272•Mar 1, 2015•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
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.
The physics and the mathematics of computation are examined to provide a foundation and perspective for the investigation of the quantum mechanics of computation. Our purpose is to explore the fundamental limits and constraints imposed on computation by Nature through the laws of physics and the mathematics of computational complexity. Inasmuch as information storage and transmission are an integral part of computation, their physical bounds are considered. The computer is viewed both physically and mathematically as a dynamical system, and is depicted in terms of the basic Turing machine paradigm. Three fundamental classes of the Turing machine are defined; the deterministic, stochastic and quantum Turing machines. Hamiltonian models and physical realizations of quantum computing are described. Quantum computers can perform some tasks which have no classical analogue, but they cannot compute functions that are non-computable by classical means. Some classically intractable problems can be solved with quantum computers.
This article underscores the pivotal role of quantum computing and related technologies in advancing Communication, Navigation, Sensing, and Services Integration (CONASENSE) in the 6G realm. The study provides a methodical journey through the chronological development of computing paradigms, starting from foundational computational frameworks like Turing Machines and Von Neumann's architecture, culminating in a sophisticated understanding of Quantum Turing Machines. Tracing computing's evolution from Turing Machines to Quantum Turing Machines, it acknowledges contributions from scientists like Bohr, Einstein, Feynman, and Benioff to quantum theory. The convergence of Quantum Computing and AI offers solutions to complex, NP-hard challenges, heralding a new era of optimization. This includes Quantum Computing, Quantum Algorithms, Quantum Machine Learning (QML), Quantum Communications, Quantum Sensing & Metrology, Quantum Simulation, and Quantum Imaging within the emerging CONASENSE and 6G paradigms, projecting their sustained relevance and impact beyond 2030.
The number of steps required in order to maximize a Bell inequality for arbitrary number of qubits is shown to grow exponentially with either the number of steps and the number of parties involved. The proof that the optimization of such correlation measure is a NP-problem is based on an operational perspective involving a Turing machine, which follows a general algorithm. The implications for the computability of the so called {\it nonlocality} for any number of qubits is similar to recent results involving entanglement or similar quantum correlation-based measures.