Efficient Quantum Emulation of Unknown Unitaries

We propose a quantum algorithm, termed the universal quantum emulator, that emulates the action of an unknown unitary transformation or its inverse on a given input state, using multiple copies of some unknown sample input states of the unitary and their corresponding output states. The algorithm does not assume any prior information about the unitary to be emulated, the sample input states, or the relation between them. We rigorously prove that if the sample input states are tomographically complete, such that the action of an unknown unitary on the input subspace can be uniquely determined by its action on the sample input states, then our proposed algorithm succeeds in generating the desired output, with an error that becomes arbitrarily small by increasing the number of copies of the samples. Remarkably, the run-time of the algorithm is logarithmic in <a:math xmlns:a="http://www.w3.org/1998/Math/MathML" display="inline"><a:mi>D</a:mi></a:math>, the dimension of the Hilbert space, and increases polynomially with <c:math xmlns:c="http://www.w3.org/1998/Math/MathML" display="inline"><c:mi>d</c:mi></c:math>, the dimension of the subspace spanned by the sample input states. Furthermore, the sample complexity of the algorithm—i.e., the total number of copies of the sample input-output pairs needed to run the algorithm—is independent of <e:math xmlns:e="http://www.w3.org/1998/Math/MathML" display="inline"><e:mi>D</e:mi></e:math> and polynomial in <g:math xmlns:g="http://www.w3.org/1998/Math/MathML" display="inline"><g:mi>d</g:mi></g:math>. In contrast, the run-time and sample complexity of algorithms that perform tomography on the sample states are both linear in <i:math xmlns:i="http://www.w3.org/1998/Math/MathML" display="inline"><i:mi>D</i:mi></i:math>. This algorithm can be used as a subroutine in other algorithms, such as quantum phase estimation. We discuss some applications of this algorithm in areas including complexity theory, secure quantum computation, and quantum resource theories.