Quantum Computing with black-box Subroutines

Abstract

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.

8 pages, 5 figures, this version citations have been shifted

References in corpus (6)

• Quantum algorithm for solving linear systems of equations
• Transforming quantum operations: quantum supermaps
• Adding control to arbitrary unknown quantum operations
• Implementing quantum control for unknown subroutines
• Flexible resources for quantum metrology
• Coherent controlization using superconducting qubits

Cited by in corpus (21)

• Photonic quantum information processing: a concise review
• Quantum Software Engineering: Landscapes and Horizons
• Quantum Shannon theory with superpositions of trajectories
• Communication through coherent control of quantum channels
• Computational advantage from quantum superposition of multiple temporal orders of photonic gates
• Entanglement spectroscopy with a depth-two quantum circuit
• Quantum operations with indefinite time direction
• Complex conjugation supermap of unitary quantum maps and its universal implementation protocol
• Modular Quantum Computation in a Trapped Ion System
• Routed quantum circuits
• A prototype of quantum von Neumann architecture
• Experimental superposition of time directions
• Controlled quantum operations and combs, and their applications to universal controllization of divisible unitary operations
• Superposing pure quantum states with partial prior information
• Universal control of quantum processes using sector-preserving channels
• Quantum communication through devices with indefinite input-output direction
• Quantum networks boosted by entanglement with a control system
• Universal resources for quantum computing
• Impossibility of creating a superposition of unknown quantum states
• Topological obstructions to quantum computation with unitary oracles
• Giving Operational Meaning to the Superposition of Causal Orders