We present setups for the practical realization of adding control to unknown subroutines, supplementing the existing quantum optical scheme for black-box control with a counterpart for the quantum control of the ordering of sequences of operations. We also provide schemes to realize either task using trapped ions. These practical circumventions of recent no-go theorems are based on existing technologies. We argue that the possibility to add control to unknown operations in practice is a common feature of many physical systems. Based on the proposed implementations we discuss the apparent contradictions between theory and practice.
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.
An essential element of classical computation is the ``if-then'' construct, that accepts a control bit and an arbitrary gate, and provides conditional execution of the gate depending on the value of the controlling bit. On the other hand, quantum theory prevents the existence of an analogous universal construct accepting a control qubit and an arbitrary quantum gate as its input. Nevertheless, there are controllable sets of quantum gates for which such a construct exists. Here we provide a necessary and sufficient condition for a set of unitary transformations to be controllable, and we give a complete characterization of controllable sets in the two-dimensional case. This result reveals an interesting connection between the problem of controllability and the problem of extracting information from an unknown quantum gate while using it.
The no-cloning theorem, the no-deleting theorem, and other no-go theorems play a crucial role in quantum mechanics and quantum information. In this paper, we show that it is impossible to conjugate or reflect an unknown quantum state or conjugate or reflect the bit-flip (the phase-flip) of an unknown state via a universally unitary evolution. We also indicate that the partial conjugating operations are not anti-unitary and it is impossible to universally partially conjugate an unknown state via a unitary evolution. We compute the fidelities of the optimal physical approximations to conjugating and conjugating the bit-flip and phase-flip operations.
Modern programming relies on our ability to treat preprogrammed functions as black boxes - we can invoke them as subroutines without knowing their physical implementation. Here we show it is generally impossible to execute an unknown quantum subroutine. This, as a special case, forbids applying black-box subroutines conditioned on an ancillary qubit. We explore how this limits many quantum algorithms - forcing their circuit implementation to be individually tailored to specific inputs and inducing failure if these inputs are not known in advance. We present a method to avoid this situation for certain computational problems. We apply this method to enhance existing quantum factoring algorithms; reducing their complexity, and the extent to which they need to be tailored to factor specific numbers. Thus, we highlight a natural property of classical information that fails in the advent of quantum logic; and simultaneously demonstrate how to mitigate its effects in practical situations.
Any unknown unitary operations conditioned on a control system can be deterministically performed if ancillary subspaces are available for the target systems [Zhou X Q, et al. 2011 Nat. Commun. 2 413]. In this paper, we show that previous optical schemes may be extended to general hybrid systems if unknown operations are provided by optical instruments. Moreover, a probabilistic scheme is proposed when the unknown operation may be performed on the subspaces of ancillary high-dimensional systems. Furthermore, the unknown operations conditioned on the multi-control system may be reduced to the case with a control system using additional linear circuit complexity. The new schemes may be more flexible for different systems or hybrid systems.