Abstract I consider a promise problem for an unknown unitary acting on an
(n)-qubit register. The oracle is promised to implement either a fixed permutation of computational basis states or the same permutation accompanied by a conditional sign change determined by a designated input qubit. I show that the two cases can be distinguished exactly with a single query to the oracle and a measurement on only one qubit, and that the query complexity of this task is exactly one. The protocol uses no ancilla qubits and requires only
(n+1) Hadamard gates in addition to the oracle call. The promise is intrinsically quantum because the two cases differ only through relative phases. MSC Classification: 81P68 , 68Q12
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.
Is a quantum algorithm capable of implementing an if-clause? Given a black-box subroutine, a
d-dimensional unitary
U∈U(d), a quantum if-clause would correspond to applying it to an input qudit if and only if the value of a control qubit is
1. It was previously shown by Thompson et al. and Araujo et al. that implementations using single access to the oracle
U are impossible. Our main result is a strong generalization of this impossibility result: we prove that there is no unitary oracle algorithm implementing $control_\phi(U)=\left|0\right>\!\!\left \!\!\left<1\right|\otimes U$, for some
U-dependent phase
ϕ(U), even if allowed any finite number of calls to
U and
U†, and even if required to only approximate the desired operator
controlϕ(U). Even further, there is no such \emph{postselection} oracle algorithm, i.e. a unitary oracle algorithm followed by a binary success/fail measurement, that reports success and implements
controlϕ(U) with a nonzero probability for each
U∈U(d).
Our proof relies on topological arguments which can be viewed as a modification of the Borsuk-Ulam theorem. Combining the topological arguments with the algorithm of Dong et al. in fact leads to an interesting dichotomy: implementing
controlϕ(Um) in our model is possible if and only if the integer
m is a multiple of the oracle's dimension
d.
Our impossibility no longer holds if the model is relaxed, either by dropping the worst-case requirement that the algorithm works for all
U∈U(d), or, remarkably, by allowing measurements more general than a binary postselection measurement. We observe that for both relaxations, inefficient algorithms exist, and it remains open whether efficient ones do.
Quantum state discrimination is one of the most fundamental tasks in quantum information since it describes the read-out process of classical information from quantum states in quantum communications.In quantum state discrimination, a given test state is guaranteed to be identical to one of a set of candidate quantum states.The task is to determine the identity of the test state by performing an appropriate quantum measurement based on the classical descriptions of the candidate states.Quantum state discrimination also has several connections to the principles of quantum mechanics such as the no-cloning theorem and the no-signaling principle.One of fundamental properties of quantum mechanics is that the exact classical description of unknown quantum states cannot be retrieved from a single copy of the physical state.Quantum state discrimination in the case that the candidate states are given as two unknown physical states (reference states) but their classical descriptions are not given, has been investigated.The two reference states are labeled one and two, respectively.The task is to determine which of the two reference states is equivalent to the test state, whereas the descriptions of the states are not of interest.We call such a task as equivalence determination of quantum states.Discrimination of quantum operations has been also investigated and it has been shown that there is an intrinsic difference between discrimination of quantum state and discrimination of quantum operations.We analyze a unitary operation version of the equivalence determination task by using the concept of higher-order quantum computation to investigate properties of discrimination of other quantum objects.We consider three black-boxes (test box and reference boxes) implementing unknown unitary operations given as physical systems.The test box is guaranteed to implement one of the two unitary operations given by the reference boxes.Equivalence determination of unitary operations is a task to determine the reference box implementing the same unitary operation as the one by the test box.We assume that the unitary operations of the reference boxes are randomly sampled from the Haar measure of SU(2).We first consider the case that each of three black-boxes can be used only once both in parallel and ordered uses of the black-boxes.We show that the optimal success probability for equivalence determination is 7/8 by obtaining analytical solutions of the corresponding semidefinite programmings (SDPs) both in the parallel and ordered strategies.The optimal success probability can be achieved even without using one of the reference boxes.We also showed that entanglement of an initial state across the systems on which the reference boxes act and the test box acts is necessary to achieve the optimal success probability.We then consider the case that the multiple uses of the reference boxes are allowed.We consider the parallel strategies up to four uses of each of the reference boxes and obtain the optimal success probabilities by numerically solving the semidefinite programmings.We numerically show that the ordered strategies give improvement over the parallel strategies and the optimal success probability varies depending on the order of the black-boxes when one reference box is used once and the other reference box is used twice.This result indicates that an appropriate order of the black-boxes under the ordered strategies is necessary to obtain improvement over the parallel strategies. Chapter 1 Introduction Notations• H i , K j : Hilbert spaces labeled with i and j.• L(H): The set of linear operators on H.• L(H, K): The set of linear operators from H to K.• S(H) : The set of positive semidefinite linear operation of unit trace on H • Tr H : The partial trace over H • U † : The conjugate transpose of U • {Π i }: The positive operator-valued measure • { Π i }: The quantum tester • δ ij : The Kronecker delta, equal to 1 if i = j and 0 otherwise • dµ(•) : The Haar measure, the uniform distribution of the space of unitary operations • |I⟩⟩ : Unnormalized maximally entangled vector defined as |I⟩⟩ = i |i⟩|i⟩ • M : A quantum channel • M : Choi operator of a quantum channel M• U j : The irreducible subspace of the total angular momentum j.
We consider the task of deciding whether an unknown qubit state falls in a prescribed neighborhood of a reference state. We assume that several copies of the unknown state are given and apply a unitary operation pairwise on them combined with a postselection scheme conditioned on the measurement result obtained on one of the qubits of the pair. The resulting transformation is a deterministic, nonlinear, chaotic map in the Hilbert space. We derive a class of these transformations capable of orthogonalizing nonorthogonal qubit states after a few iterations. These nonlinear maps orthogonalize states which correspond to the two different convergence regions of the nonlinear map. Based on the analysis of the border (the so-called Julia set) between the two regions of convergence, we show that it is always possible to find a map capable of deciding whether an unknown state is within a neighborhood of fixed radius around a desired quantum state. We analyze which one- and two-qubit operations would physically realize the scheme. It is possible to find a single two-qubit unitary gate for each map or, alternatively, a universal special two-qubit gate together with single-qubit gates in order to carry out the task. We note that it is enough to have a single physical realization of the required gates due to the iterative nature of the scheme.
We characterize a model of universal quantum computation where the register (computational) qubits are controlled by ancillary qubits, using only a single fixed interaction between register and ancillary qubits. No additional access is required to the computational register and the dynamics of both the register and ancilla are unitary. This scheme is inspired by the measurement-based ancilla-driven quantum computation of Anders et al. [Phys. Rev. A 82, 020301(R) (2010)], but does not require measurements of the ancillas, and in this respect is similar to the original gate-based model of quantum computation. We consider what possible forms this ancilla-register interaction can take, with a proof that the interaction is necessarily locally equivalent to swap combined with an entangling controlled gate. We further show which Hamiltonians can create such interactions and discuss two examples; the two-qubit XY Hamiltonian and a particular case of the XXZ Hamiltonian. We then give an example of a simple, finite, and fault-tolerant gate set for universal quantum computation in this model.