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.
Let H1,H2 be Hilbert spaces of the same finite dimension ≥2, and C an arbitrary quantum circuit with (principal) input state in H1 and (principal) output state in H2. 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 μ through the circuit, a unitary transformation Uμ:H1→H2 then, for each μ, the probability that a computation takes path μ is independent of the input.
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 introduce the problem of unitarization. Unitarization is the problem of taking k input quantum circuits that produce orthogonal states from the all 0 state, and create an output circuit implementing a unitary with its first k columns as those states. That is, the output circuit takes the kth computational basis state to the state prepared by the kth input circuit. We allow the output circuit to use ancilla qubits initialized to 0. But ancilla qubits must always be returned to 0 for any input. The input circuits may use ancilla qubits, but we are only guaranteed the they return ancilla qubits to 0 on the all 0 input. The unitarization problem seems hard if the output states are neither orthogonal to or in the span of the computational basis states that need to map to them. In this work, we approximately solve this problem in the case where input circuits are given as black box oracles by probably finding an approximate basis for our states. This method may be more interesting than the application. This technique is a sort of quantum analogue of Gram-Schmidt orthogonalization for quantum states. Specifically, we find an approximate basis in polynomial time for the following parameters. Take any natural n, k=O(ln(ln(n))ln(n)), and ε=2−O(ln(n)). Take any k input quantum states, (∣ψi⟩)i∈[k], on polynomial in n qubits prepared by quantum oracles, (Vi)i∈[k] (that we can control call and control invert). Then there is a quantum circuit with polynomial size in n with access to the oracles (Vi)i∈[k] that with at least 1−ε probability, computes at most k circuits with size polynomial in n and oracle access to (Vi)i∈[k] that ε approximately computes an ε approximate orthonormal basis for (∣ψi⟩)i∈[k].
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
One-way measurement based quantum computations (1WQC) may describe unitary transformations, via a composition of CPTP maps which are not all unitary themselves. This motivates the following decision problems. Is it possible to determine whether a "quantum-to-quantum" 1WQC procedure (having non-trivial input and output subsystems) performs a unitary transformation? Is it possible to describe precisely how such computations transform quantum states, by translation to a quantum circuit of comparable complexity? In this article, we present an efficient algorithm for transforming certain families of measurement-based computations into a reasonable unitary circuit model, in particular without employing the principle of deferred measurement.
Summary form only given, as follows. Gives a system theoretic approach to the concept of quantum computing. A quantum computer is envisaged to be a system of quantum circuits, acting on a state space, which is a finite-say 2/sup n/-dimensional-complex Hilbert space. The circuitry is a sequence of unitary transforms U/sub t/ /spl epsiv/ SU(2/sup n/) followed by a measurement. These transforms, so-called quantum gates, are controlled by a classical computer, usually especially electromagnetic fields. The state space of a quantum computer has the structure of a Hermitian vector space. Thus it allows "simultaneous" superposition of orthogonal basis states (corresponding to classical states) with the possibility of constructive and destructive interference between different paths of computation. This principle allows the usage of so-called entangled states by preparing the superposition of special "bent" configurations of basis vectors in the product Hilbert space, e.g., as they are known from error control and cryptography. This latter "entanglement" not only promises to make a quantum computer much more powerful than a probabilistic one, but it also allows a method of parallelism. The reason for this lies not only in the fact that the 2/sup n/ dimensional Hilbert space is the n-fold tensor product of 2-dimensional spaces as it is given by spin-1/2-particles, like photons, representing a quantum bit. First of all, we shall address the fact that the power of quantum computing lies in the properties of entangled states as opposed to those of separable states which essentially would resemble classical circuits without giving the feature of exponential speed-up. We shall briefly describe possible physical realisations of quantum (optic, electronic, magnetic,...) devices allowing the engineering of Hamiltonians needed for quantum systems. Basic quantum gates, especially the quantum Horner-Toffoli gate will be discussed to display the principles and methodology for designing quantum circuits. An outlook towards the possible availability of nano- and mesoscopic technologies supporting this new architecture in future generations concludes based on a speculative worst/best case forecast of possible applications, e.g., in public key and conventional cryptography.
Let H1, H2 be complex Hilbert spaces, H be their Hilbert tensor product and let tr2 be the operator of taking partial trace, with respect to the space H2, of trace class operators in H. The operation tr2 maps states in H (=positive trace class operators in H with trace equal to 1) into states in H1. In this paper we give the full description of mappings that are linear right inverse to tr2. More precisely, we prove that any affine mapping F(W) of the convex set of states in H1 into the states in H that is right inverse to tr2 is given by W⟼W⊗D for some state D in H2. In addition we investigate a representation of the quantum mechanical state space by probability measures on the set of pure states and a representation—used in the theory of stochastic Schrödinger equations—by probability measures on the Hilbert space. We prove that there are no affine mappings from the state space of quantum mechanics into these spaces of probability measures.