In this paper, I take a step toward answering the following question: for m different small circuits that compute m orthogonal n qubit states, is there a small circuit that will map m computational basis states to these m states without any input leaving any auxiliary bits changed. While this may seem simple, the constraint that auxiliary bits always be returned to 0 on any input (even ones besides the m we care about) led me to use sophisticated techniques. I give an approximation of such a unitary in the m = 2 case that has size polynomial in the approximation error, and the number of qubits n.
In this paper, I take a step toward answering the following question: for m different small circuits that compute m orthogonal n qubit states, is there a small circuit that will map m computational basis states to these m states without any input leaving any auxiliary bits changed. While this may seem simple, the constraint that auxiliary bits always be returned to 0 on any input (even ones besides the m we care about) led me to use sophisticated techniques. I give an approximation of such a unitary in the m = 2 case that has size polynomial in the approximation error, and the number of qubits n.
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].
While the question ``how many CNOT gates are needed to simulate an arbitrary two-qubit operator'' has been conclusively answered -- three are necessary and sufficient -- previous work on this topic assumes that one wants to simulate a given unitary operator up to global phase. However, in many practical cases additional degrees of freedom are allowed. For example, if the computation is to be followed by a given projective measurement, many dissimilar operators achieve the same output distributions on all input states. Alternatively, if it is known that the input state is ∣0⟩, the action of the given operator on all orthogonal states is immaterial. In such cases, we say that the unitary operator is incompletely specified; in this work, we take up the practical challenge of satisfying a given specification with the smallest possible circuit. In particular, we identify cases in which such operators can be implemented using fewer quantum gates than are required for generic completely specified operators.
The action of a NOT gate on a classical bit results in a change of its value from a 0 to a 1 and vice versa. The action of the classical NOT gate is in principle perfect because with fidelity equal to unity it complements the value of a bit. The action of the quantum NOT gate in a computational basis |0⟩ and |1⟩ is very similar to the action of the classical NOT gate. However, a more general quantum mechanical operation which corresponds to a classical NOT gate would take a qubit in an arbitrary state |Ψ⟩ and produce a qubit in the state |Ψ⊥⟩ orthogonal to |Ψ⟩. This operation is anti-unitary and therefore, cannot be realized exactly. So how well we can do? We find a unitary transformation acting on an input qubit and some auxiliary qubits, which represent degrees of freedom of the quantum NOT gate itself, which approximately realizes the NOT operation on the state of the original qubit. We call this ‘device’ a universal-NOT gate because the size of the error it produces is independent of the input state. We show that an optimal U-NOT gate which has as its input N identical qubits and produces M outputs achieves a fidelity of F = (N + 1)/ (N + 2), which is equal to the fidelity of estimation of the input qubits. We also show that when a priori information about the state of the input qubit is available, the fidelity of a quantum NOT gate can be much better than the fidelity of estimation.
The circuit-gate framework of quantum computing relies on the fact that an arbitrary quantum gate in the form of a unitary matrix of unit determinant can be approximated to a desired accuracy by a fairly short sequence of basic gates, of which the exact bounds are provided by the Solovay–Kitaev theorem. In this work, we show that a version of this theorem is applicable to orthogonal matrices with unit determinant as well, indicating the possibility of using orthogonal matrices for efficient computation. We further develop a version of the Solovay–Kitaev algorithm and discuss the computational experience.
Suppose we want to implement a unitary U , for instance a circuit for some quantum algorithm. Suppose our actual implementation is a unitary U~ , which we can only apply as a black-box. In general it is an exponentially-hard task to decide whether U~ equals the intended U , or is significantly different in a worst-case norm. In this paper we consider two special cases where relatively efficient and lightweight procedures exist for this task.First, we give an efficient procedure under the assumption that U and U~ (both of which we can now apply as a black-box) are either equal, or differ significantly in only one k -qubit gate, where k=O(1) (the k qubits need not be contiguous). Second, we give an even more lightweight procedure under the assumption that U and U~ are Clifford circuits which are either equal, or different in arbitrary ways (the specification of U is now classically given while U~ can still only be applied as a black-box). Both procedures only need to run U~ a constant number of times to detect a constant error in a worst-case norm. We note that the Clifford result also follows from earlier work of Flammia and Liu, and da Silva, Landon-Cardinal, and Poulin.In the Clifford case, our error-detection procedure also allows us efficiently to learn (and hence correct) U~ if we have a small list of possible errors that could have happened to U ; for example if we know that only O(1) of the gates of U~ are wrong, this list will be polynomially small and we can test each possible erroneous version of U for equality with U~ .
We study minimum-error identification of an unknown single-bit Boolean function given black-box (oracle) access with one allowed query. Rather than stopping at an abstract optimal measurement, we give a fully constructive solution: an explicit state preparation and an explicit measurement unitary whose computational-basis readout achieves the Helstrom-optimal success probability 3/4 for distinguishing the four possible functions. The resulting circuit is low depth, uses a fixed gate set, and (in this smallest setting) requires no entanglement in the input state. Beyond the specific example, the main message is operational. It highlights a regime in which optimal oracle discrimination is not only well-defined but implementably explicit: the optimal POVM collapses to a compact gate-level primitive that can be compiled, verified, and composed inside larger routines. Motivated by this, we discuss a "what if" question that is open in spirit: for fixed (n,m,k), could optimal k-query identification (possibly for large hypothesis classes) admit deterministic, closed-form descriptions of the inter-query unitaries and the final measurement unitary acting on the natural n+m-qubit input--output registers (and, if needed, small work registers)? Even when such descriptions are not compact and do not evade known circuit-complexity barriers for generic Boolean functions, making the optimum constructive at the circuit level would be valuable for theory-to-hardware translation and for clarifying which forms of "oracle access" are physically meaningful.