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

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE

Probabilistic nonunitary quantum computing

Colin P. Williams

Published Aug 24, 2004• 9 citations
Publisher

Abstract

In [1] Gingrich and Williams extended the standard quantum circuit model of quantum computation to include gates that perform arbitrary linear, yet non-unitary, transformations of their input state. In this paper we use this theory to construct quantum circuits that perform desired non-unitary state transformations of the sort arising in lattice-based quantum search. Such n-qubit non-unitary gates cannot be achieved deterministically, but they can be achieved probabilistically using a single ancilla. Our approach is to use the n-qubit non-unitary gate to design an (n+1)-qubit Hamiltonian that can be seen to induce a suitable conditional dynamics such that whenever the output value of the ancilla qubit is measured and found to be |O>, then the remaining (unmeasured) n qubits will contain the desired non-unitary transform of the n-qubit input state. The scheme is necessarily probabilistic because we cannot force the measurement on the ancilla qubit to return the value we want. Fortunately, however, failed attempts are found to disturb the n-qubit input state very little. This allows us to re-use the result of successive “failed” attempts until the success condition is finally attained, and we give analytic expressions for the success probability and net fidelity in this case. By using our previous method for designing a quantum circuit for an arbitrary n-qubit gate in conjunction with our new probabilistic non-unitary procedure we are able to compute an explicit quantum circuit sufficient to implement an arbitrary linear, yet non-unitary, transformation of an input pure or mixed n-qubit state, using only a single copy of the input state. This allows us to extend the repertoire of computations that may be performed on a quantum computer, and in particular, gives the first explicit construction of the quantum circuits needed to perform some of the key operations arising in quantum lattice search.

DOI
10.1117/12.542413

Related papers

Non-unitary probabilistic quantum computing

Robert M. Gingrich, Colin P. Williams

We present a method for designing quantum circuits that perform non-unitary quantum computations on n-quhit states prohabilistically, and give analytic expressions for the suc-cess probability and fidelity. Our scheme works by embedding the desired non-unitaiy op-erator within an anti-block-diagonal (n+l)-qubit Hamiltonian, H, which induces a unitary operator!J = exp(iEH), with E a constant. By using $2 acting on the original state aug-mented with an ancilla prepared in the 11) state, we can obtain the desired nowunitary transformation whenever the ancilla is found to be IO). Our scheme has the advantage that a "failure " result, i.e., fmding the ancilla to be 11) rather than 10) , perturbs the remaining n-qubit state very little. As a result we can repeatedly re-evolve and measure the sequence of "failed " states until we fmd the ancilla in the 10) state, i.e., detect the "success " condi-tion. We describe an application of our scheme to probabilistic state synthesis, I.

•Jan 5, 2004•8 citations

A Quantum Model of Computation

Phillip Kaye, Raymond Laflamme, Michele Mosca

In Section 1.3, we introduced the circuit model of (classical) computation. We restricted attention to reversible circuits since they can simulate any non-reversible circuit with modest overhead. This model can be generalized to a model of quantum circuits. In the quantum circuit model, we have logical qubits carried along ‘wires’, and quantum gates that act on the qubits. A quantum gate acting on n qubits has the input qubits carried to it by n wires, and n other wires carry the output qubits away from the gate. A quantum circuit is often illustrated schematically by a circuit diagram as shown in Figure 4.1. The wires are shown as horizontal lines, and we imagine the qubits propagating along the wires from left to right in time. The gates are shown as rectangular blocks. For convenience, we will restrict attention to unitary quantum gates (which are also reversible). Recall from Section 3.5.3 that non-unitary (non-reversible) quantum operations can be simulated by unitary (reversible) quantum gates if we allow the possibility of adding an ancilla and of discarding some output qubits. A circuit diagram describing a superoperator being implemented using a unitary operator is illustrated in Figure 4.2. In the example of Figure 4.1, the 4-qubit state |ψi⟩= |0⟩⊗ |0⟩⊗ |0⟩⊗ |0⟩ enters the circuit at the left (recall we often write this state as |ψi⟩ = |0⟩|0⟩|0⟩|0⟩ or |ψi⟩ = |0000⟩.) These qubits are processed by the gates U1, U2, U3, and U4. At the output of the circuit we have the collective (possibly entangled) 4-qubit state |ψf⟩. A measurement is then made of the resulting state. The measurement will often be a simple qubit-by-qubit measurement in the computational basis, but in some cases may be a more general measurement of the joint state. A measurement of a single qubit in the computational basis is denoted on a circuit diagram by a small triangle, as shown in Figure 4.1 (there are other symbols used in the literature, but we adopt this one). The triangle symbol will be modified for cases in which there is a need to indicate different types of measurements.R50

Oxford University Press eBooks•Nov 16, 2006•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

NONUNITARY QUANTUM CIRCUIT

HIROAKI TERASHIMA, MASAHITO UEDA

A quantum circuit is generalized to a nonunitary one whose constituents are nonunitary gates operated by quantum measurement. It is shown that a specific type of one-qubit nonunitary gates, the controlled-NOT gate, and all one-qubit unitary gates constitute a universal set of gates for the nonunitary quantum circuit, without the necessity of introducing ancilla qubits. A reversing measurement scheme is used to improve the probability of successful nonunitary gate operation. A quantum NAND gate and Abrams–Lloyd's nonlinear gate are analyzed as examples. Our nonunitary circuit can be used to reduce the qubit overhead needed to ensure fault-tolerant quantum computation.

arXiv:quant-ph/0304061•International Journal of Quantum Information•Dec 1, 2005•81 citations

Quantum circuits computing unitary transformations

Andreas R. Blass, Yuri G. Gurevich

Let $H_1, H_2$ be Hilbert spaces of the same finite dimension $\ge2$, and $C$ an arbitrary quantum circuit with (principal) input state in $H_1$ and (principal) output state in $H_2$. $C$ may use ancillas and produce garbage which is traced out. $C$ may employ classical channels and measurement gates. If $C$ computes, for each computation path $\mu$ through the circuit, a unitary transformation $U_\mu: H_1 \to H_2$ then, for each $\mu$, the probability that a computation takes path $\mu$ is independent of the input.

•May 30, 2021•0 citations

Probabilistic exact universal quantum circuits for transforming unitary operations

Marco Túlio Quintino, Qingxiuxiong Dong, Atsushi Shimbo +2 more

This paper addresses the problem of designing universal quantum circuits to transform $k$ uses of a $d$-dimensional unitary input operation into a unitary output operation in a probabilistic heralded manner. Three classes of protocols are considered, parallel circuits, where the input operations can be performed simultaneously, adaptive circuits, where sequential uses of the input operations are allowed, and general protocols, where the use of the input operations may be performed without a definite causal order. For these three classes, we develop a systematic semidefinite programming approach that finds a circuit which obtains the desired transformation with the maximal success probability. We then analyze in detail three particular transformations: unitary transposition, unitary complex conjugation, and unitary inversion. For unitary transposition and unitary inverse, we prove that for any fixed dimension $d$, adaptive circuits have an exponential improvement in terms of uses $k$ when compared to parallel ones. For unitary complex conjugation and unitary inversion we prove that if the number of uses $k$ is strictly smaller than $d\ensuremath{-}1$, the probability of success is necessarily zero. We also discuss the advantage of indefinite causal order protocols over causal ones and introduce the concept of delayed input-state quantum circuits.

arXiv:1909.01366•Physical Review A•Dec 30, 2019•73 citations
In [1] Gingrich and Williams extended the standard quantum circuit model of quantum computation to include gates that perform arbitrary linear, yet non-unitary, transformations of their input state. In this paper we use this theory to construct quantum circuits that perform desired non-unitary state transformations of the sort arising in lattice-based quantum search. Such n-qubit non-unitary gates cannot be achieved deterministically, but they can be achieved probabilistically using a single ancilla. Our approach is to use the n-qubit non-unitary gate to design an (n+1)-qubit Hamiltonian that can be seen to induce a suitable conditional dynamics such that whenever the output value of the ancilla qubit is measured and found to be |O>, then the remaining (unmeasured) n qubits will contain the desired non-unitary transform of the n-qubit input state. The scheme is necessarily probabilistic because we cannot force the measurement on the ancilla qubit to return the value we want. Fortunately, however, failed attempts are found to disturb the n-qubit input state very little. This allows us to re-use the result of successive “failed” attempts until the success condition is finally attained, and we give analytic expressions for the success probability and net fidelity in this case. By using our previous method for designing a quantum circuit for an arbitrary n-qubit gate in conjunction with our new probabilistic non-unitary procedure we are able to compute an explicit quantum circuit sufficient to implement an arbitrary linear, yet non-unitary, transformation of an input pure or mixed n-qubit state, using only a single copy of the input state. This allows us to extend the repertoire of computations that may be performed on a quantum computer, and in particular, gives the first explicit construction of the quantum circuits needed to perform some of the key operations arising in quantum lattice search.
We present a method for designing quantum circuits that perform non-unitary quantum computations on n-quhit states prohabilistically, and give analytic expressions for the suc-cess probability and fidelity. Our scheme works by embedding the desired non-unitaiy op-erator within an anti-block-diagonal (n+l)-qubit Hamiltonian, H, which induces a unitary operator!J = exp(iEH), with E a constant. By using $2 acting on the original state aug-mented with an ancilla prepared in the 11) state, we can obtain the desired nowunitary transformation whenever the ancilla is found to be IO). Our scheme has the advantage that a "failure " result, i.e., fmding the ancilla to be 11) rather than 10) , perturbs the remaining n-qubit state very little. As a result we can repeatedly re-evolve and measure the sequence of "failed " states until we fmd the ancilla in the 10) state, i.e., detect the "success " condi-tion. We describe an application of our scheme to probabilistic state synthesis, I.
In Section 1.3, we introduced the circuit model of (classical) computation. We restricted attention to reversible circuits since they can simulate any non-reversible circuit with modest overhead. This model can be generalized to a model of quantum circuits. In the quantum circuit model, we have logical qubits carried along ‘wires’, and quantum gates that act on the qubits. A quantum gate acting on n qubits has the input qubits carried to it by n wires, and n other wires carry the output qubits away from the gate. A quantum circuit is often illustrated schematically by a circuit diagram as shown in Figure 4.1. The wires are shown as horizontal lines, and we imagine the qubits propagating along the wires from left to right in time. The gates are shown as rectangular blocks. For convenience, we will restrict attention to unitary quantum gates (which are also reversible). Recall from Section 3.5.3 that non-unitary (non-reversible) quantum operations can be simulated by unitary (reversible) quantum gates if we allow the possibility of adding an ancilla and of discarding some output qubits. A circuit diagram describing a superoperator being implemented using a unitary operator is illustrated in Figure 4.2. In the example of Figure 4.1, the 4-qubit state |ψi⟩= |0⟩⊗ |0⟩⊗ |0⟩⊗ |0⟩ enters the circuit at the left (recall we often write this state as |ψi⟩ = |0⟩|0⟩|0⟩|0⟩ or |ψi⟩ = |0000⟩.) These qubits are processed by the gates U1, U2, U3, and U4. At the output of the circuit we have the collective (possibly entangled) 4-qubit state |ψf⟩. A measurement is then made of the resulting state. The measurement will often be a simple qubit-by-qubit measurement in the computational basis, but in some cases may be a more general measurement of the joint state. A measurement of a single qubit in the computational basis is denoted on a circuit diagram by a small triangle, as shown in Figure 4.1 (there are other symbols used in the literature, but we adopt this one). The triangle symbol will be modified for cases in which there is a need to indicate different types of measurements.R50
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.
A quantum circuit is generalized to a nonunitary one whose constituents are nonunitary gates operated by quantum measurement. It is shown that a specific type of one-qubit nonunitary gates, the controlled-NOT gate, and all one-qubit unitary gates constitute a universal set of gates for the nonunitary quantum circuit, without the necessity of introducing ancilla qubits. A reversing measurement scheme is used to improve the probability of successful nonunitary gate operation. A quantum NAND gate and Abrams–Lloyd's nonlinear gate are analyzed as examples. Our nonunitary circuit can be used to reduce the qubit overhead needed to ensure fault-tolerant quantum computation.
Let H1,H2H_1, H_2H1​,H2​ be Hilbert spaces of the same finite dimension ≥2\ge2≥2, and CCC an arbitrary quantum circuit with (principal) input state in H1H_1H1​ and (principal) output state in H2H_2H2​. CCC may use ancillas and produce garbage which is traced out. CCC may employ classical channels and measurement gates. If CCC computes, for each computation path μ\muμ through the circuit, a unitary transformation Uμ:H1→H2U_\mu: H_1 \to H_2Uμ​:H1​→H2​ then, for each μ\muμ, the probability that a computation takes path μ\muμ is independent of the input.
This paper addresses the problem of designing universal quantum circuits to transform kkk uses of a ddd-dimensional unitary input operation into a unitary output operation in a probabilistic heralded manner. Three classes of protocols are considered, parallel circuits, where the input operations can be performed simultaneously, adaptive circuits, where sequential uses of the input operations are allowed, and general protocols, where the use of the input operations may be performed without a definite causal order. For these three classes, we develop a systematic semidefinite programming approach that finds a circuit which obtains the desired transformation with the maximal success probability. We then analyze in detail three particular transformations: unitary transposition, unitary complex conjugation, and unitary inversion. For unitary transposition and unitary inverse, we prove that for any fixed dimension ddd, adaptive circuits have an exponential improvement in terms of uses kkk when compared to parallel ones. For unitary complex conjugation and unitary inversion we prove that if the number of uses kkk is strictly smaller than $d\ensuremath{-}1$, the probability of success is necessarily zero. We also discuss the advantage of indefinite causal order protocols over causal ones and introduce the concept of delayed input-state quantum circuits.