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.
Dr. Jayne Thompson graduated her Ph.D. from the University of Melbourne in theoretical particle physics. Since then, she has turned her attention to foundational questions in the theory of quantum computation and quantum information. She currently works as a research fellow with Vlatko Vedral at the Centre for Quantum Technologies, National University of Singapore.