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

The Non-mechanistic Character of Quantum Computation

Giuseppe Castagnoli, Dalida Monti

Published Nov 16, 1998• 5 citations
arXivHTMLPDF

Abstract

The higher than classical efficiency exhibited by some quantum algorithms is here ascribed to their non-mechanistic character, which becomes evident by joining the notions of entanglement and quantum measurement. Measurement analogically sets a (partial) constraint on the output of the computation of a hard-to-reverse function. This constraint goes back in time along the reversible computation process, computing the reverse function, which yields quantum efficiency. The evolution, comprising wave function collapse (here a revamped notion), is non-mechanistic as it is driven by both an initial condition and a final constraint. It seems that the more the output is constrained by measurement, the higher can be the efficiency. Setting a complete constraint, by means of a special Zeno effect, yields (speculatively) NP-complete=P.

DOI
10.48550/arxiv.quant-ph/9811039

Related papers

Symmetry, Reversibility, and Efficiency of Quantum Computation

Giuseppe Castagnoli, Dalida Monti, Alexander V. Sergienko

The reason for the higher efficiency exhibited by some quantum algorithms over their classical counterparts is examined by considering the interplay between the reversible actions required to prepare the computer registers in an entangled state before measurement (the "initial actions"), and the final measurement action -- whereas measurement is interpreted in a new way, particularly suited to a problem solving context. This unification shows that the computation process, comprising the measurement outcome, is significantly influenced by both the initial actions and the need to satisfy the constraints set by the final measurement action. Reviewing the existing quantum algorithms in the light of this dual influence, yields new valuable insight in the nature of the quantum computation speed up.

arXiv:quant-ph/9908015•Aug 4, 1999•0 citations

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

Giuseppe Castagnoli

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.

arXiv:quant-ph/9810017•Oct 6, 1998•1 citation

A Quantum Logic Gate Representation of Quantum Measurement: Reversing and Unifying the Two Steps of von Neumann's Model

Giuseppe Castagnoli

In former work, quantum computation has been shown to be a problem solving process essentially affected by both the reversible dynamics leading to the state before measurement, and the logical-mathematical constraints introduced by quantum measurement (in particular, the constraint that there is only one measurement outcome). This dual influence, originated by independent initial and final conditions, justifies the quantum computation speed-up and is not representable inside dynamics, namely as a one-way propagation. In this work, we reformulate von Neumann's model of quantum measurement at the light of above findings. We embed it in a broader representation based on the quantum logic gate formalism and capable of describing the interplay between dynamical and non-dynamical constraints. The two steps of the original model, namely (1) dynamically reaching a complete entanglement between pointer and quantum object and (2) enforcing the one-outcome-constraint, are unified and reversed. By representing step (2) right from the start, the same dynamics of step (1) yields a probability distribution of mutually exclusive measurement outcomes. This appears to be a more accurate and complete representation of quantum measurement. PACS: 03.67.-a, 03.67.Lx, 03.65.Bz

arXiv:quant-ph/9912020•Dec 6, 1999•3 citations

Quantum Computation Beyond the Unitary Circuit Model

Naïri Usher

This thesis considers various paradigms of quantum computation in an attempt to understand the nature of the underlying physics. A standard approach is to consider unitary computation on pure input states, such that the outcome of the computation is determined by single computational basis measurement on the output state. It has been shown that there exists equivalent models of computation, such as measurement based quantum computing (MBQC), which provide insight into the role of entanglement and measurement. Furthermore, constraining or relaxing available resources can directly impacts the power of the computation, allowing one to gauge their role in the process. Here, we first extend known constructions such as Matrix Product States, MBQC and the oneclean qubit model to a mixed state formalism, in an attempt to develop computational models where noise acting on the physical resources, as might be experienced in laboratory settings, may be mapped to logical noise on the computation. Next, we introduce Measurement-Based Classical Computing, an essentially classical model of computation, wherein the complexity hard wired into probability distributions generated via quantum means yields surprising non classical results. Finally, we consider postselection the ability to discard displeasing measurement outcomes and argue that it may be used in a tame way, which does not provide a dramatic increase in computational power. From here, we develop a new Hamiltonian, based on a circuit to Hamiltonian construction, presenting evidence of QMA-hardness.

•Jun 28, 2017•0 citations

Quantum Zeno Effect in the Measurement Problem

Mikio Namiki, Saverio Pasaczio

Critically analyzing the so-called quantum Zeno effect in the measurement problem, we show that observation of this effect does not necessarily mean experimental evidence for the naive notion of wave-function collapse by measurement (the simple projection rule). We also examine what kind of limitation the uncertainty relation and others impose on the observation of the quantum Zeno effect.

•Jan 1, 1996•0 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 higher than classical efficiency exhibited by some quantum algorithms is here ascribed to their non-mechanistic character, which becomes evident by joining the notions of entanglement and quantum measurement. Measurement analogically sets a (partial) constraint on the output of the computation of a hard-to-reverse function. This constraint goes back in time along the reversible computation process, computing the reverse function, which yields quantum efficiency. The evolution, comprising wave function collapse (here a revamped notion), is non-mechanistic as it is driven by both an initial condition and a final constraint. It seems that the more the output is constrained by measurement, the higher can be the efficiency. Setting a complete constraint, by means of a special Zeno effect, yields (speculatively) NP-complete=P.
The reason for the higher efficiency exhibited by some quantum algorithms over their classical counterparts is examined by considering the interplay between the reversible actions required to prepare the computer registers in an entangled state before measurement (the "initial actions"), and the final measurement action -- whereas measurement is interpreted in a new way, particularly suited to a problem solving context. This unification shows that the computation process, comprising the measurement outcome, is significantly influenced by both the initial actions and the need to satisfy the constraints set by the final measurement action. Reviewing the existing quantum algorithms in the light of this dual influence, yields new valuable insight in the nature of the quantum computation speed up.
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.
In former work, quantum computation has been shown to be a problem solving process essentially affected by both the reversible dynamics leading to the state before measurement, and the logical-mathematical constraints introduced by quantum measurement (in particular, the constraint that there is only one measurement outcome). This dual influence, originated by independent initial and final conditions, justifies the quantum computation speed-up and is not representable inside dynamics, namely as a one-way propagation. In this work, we reformulate von Neumann's model of quantum measurement at the light of above findings. We embed it in a broader representation based on the quantum logic gate formalism and capable of describing the interplay between dynamical and non-dynamical constraints. The two steps of the original model, namely (1) dynamically reaching a complete entanglement between pointer and quantum object and (2) enforcing the one-outcome-constraint, are unified and reversed. By representing step (2) right from the start, the same dynamics of step (1) yields a probability distribution of mutually exclusive measurement outcomes. This appears to be a more accurate and complete representation of quantum measurement. PACS: 03.67.-a, 03.67.Lx, 03.65.Bz
This thesis considers various paradigms of quantum computation in an attempt to understand the nature of the underlying physics. A standard approach is to consider unitary computation on pure input states, such that the outcome of the computation is determined by single computational basis measurement on the output state. It has been shown that there exists equivalent models of computation, such as measurement based quantum computing (MBQC), which provide insight into the role of entanglement and measurement. Furthermore, constraining or relaxing available resources can directly impacts the power of the computation, allowing one to gauge their role in the process. Here, we first extend known constructions such as Matrix Product States, MBQC and the oneclean qubit model to a mixed state formalism, in an attempt to develop computational models where noise acting on the physical resources, as might be experienced in laboratory settings, may be mapped to logical noise on the computation. Next, we introduce Measurement-Based Classical Computing, an essentially classical model of computation, wherein the complexity hard wired into probability distributions generated via quantum means yields surprising non classical results. Finally, we consider postselection the ability to discard displeasing measurement outcomes and argue that it may be used in a tame way, which does not provide a dramatic increase in computational power. From here, we develop a new Hamiltonian, based on a circuit to Hamiltonian construction, presenting evidence of QMA-hardness.
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.