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 introduce a model of quantum computation intermediate between the gate-based and measurement-based models. A quantum register is manipulated remotely with the help of a single ancilla that ``drives'' the evolution of the register. The fully controlled ancilla qubit is coupled to the computational register only via a fixed unitary two-qubit interaction and then measured in suitable bases, driving both single- and two-qubit operations on the register. Arbitrary single-qubit operations directly on register qubits are not needed. We characterize all interactions
E that induce a unitary, stepwise deterministic measurement back-action on the register sufficient to implement any quantum channel. Our scheme offers experimental advantages for computation, state preparation, and generalized measurements, since no tunable control of the register is required.
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.
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.
Quantum algorithms are typically understood in terms of the evolution of a multi-qubit quantum system under a prescribed sequence of unitary transformations. The input to the algorithm prescribes some of the unitary transformations in the sequence with others remaining fixed. For oracle query algorithms, the input determines the oracle unitary transformation. Such algorithms can be regarded as devices for discriminating amongst a set of unitary transformations. The question arises: "Given a set of known oracle unitary transformations, to what extent is it possible to discriminate amongst them?" We investigate this for the Deutsch-Jozsa problem. The task of discriminating amongst the admissible oracle unitary transformations results in an exhaustive collection of algorithms which can solve the problem with certainty.
We examine how to distinguish between unitary operators, when the exact form of the possible operators is not known. Instead we are supplied with ‘programs’ in the form of unitary transforms, which can be used as references for identifying the unknown unitary transform. All unitary transforms should be used as few times as possible. This situation is analogous to programmable state discrimination. One difference, however, is that the quantum state to which we apply the unitary transforms may be entangled, leading to a richer variety of possible strategies. By suitable selection of an input state and generalized measurement of the output state, both unambiguous and minimum-error discrimination can be achieved. Pairwise comparison of operators, comparing each transform to be identified with a program transform, is often a useful strategy. There are, however, situations in which more complicated strategies perform better. This is the case especially when the number of allowed applications of program operations is different from the number of the transforms to be identified.