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 D , the dimension of the Hilbert space, and increases polynomially with d , 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 D and polynomial in d . In contrast, the run-time and sample complexity of algorithms that perform tomography on the sample states are both linear in D . 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.
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 D , the dimension of the Hilbert space, and increases polynomially with d , 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 D and polynomial in d . In contrast, the run-time and sample complexity of algorithms that perform tomography on the sample states are both linear in D . 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.
We propose a quantum algorithm that emulates the action of an unknown unitary transformation 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 or the sample input states. To emulate the action of the unknown unitary, the new input state is coupled to the given sample input-output pairs in a coherent fashion. Remarkably, the runtime of the algorithm is logarithmic in D, the dimension of the Hilbert space, and increases polynomially with d, 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 D and polynomial in d. In contrast, the runtime and sample complexity of incoherent methods, i.e., methods that use tomography, are both linear in D. The algorithm is blind, in the sense that, at the end, it does not learn anything about the given samples or the emulated unitary. This algorithm can be used as a subroutine in other algorithms, such as quantum phase estimation.
We describe algorithms to obtain an approximate classical description of a d-dimensional quantum state when given access to a unitary (and its inverse) that prepares it. For pure states we characterize the query complexity for ℓq-norm error up to logarithmic factors. As a special case, we show that it takes applications of the unitaries to obtain an ε-ℓ2-approximation of the state. For mixed states we consider a similar model, where the unitary prepares a purification of the state. We characterize the query complexity for obtaining Schatten q-norm estimates of a rank-r mixed state, up to polylogarithmic factors. In particular, we show that a trace-norm (q = 1) estimate can be obtained with queries. This improves (assuming our stronger input model) the ε-dependence over the works of O'Donnell and Wright (STOC 2016) and Haah et al. (IEEE Trans. Inf. Theory, 63.9, 2017), that use a joint measurement on copies of the state. To our knowledge, the most sample-efficient results for pure-state tomography come from setting the rank to 1 in generic mixed-state tomography algorithms, which can require a large amount of computing resources. We describe sample-optimal algorithms for pure states that are simple and fast to implement. Along the way we show that an ℓ∞-norm estimate of a normalized vector induces a (slightly worse) ℓq-norm estimate for that vector, without losing a dimension-dependent factor in the precision. We also develop an unbiased and symmetric version of phase estimation, where the probability distribution of the estimate is centered around the true value. Finally, we give an efficient method for estimating multiple expectation values, improving over the recent result by Huggins et al. (arXiv:2111.09283) when the measurement operators do not fully overlap. More specifically, we show that for E1,…, Em normalized measurement operators, all expectation values Tr(Ejρ) can be efficiently learned up to error ε with applications of a state-preparation unitary for a purification of ρ. * The full version of the paper can be accessed at https://arxiv.org/abs/2207.08800
We describe algorithms to obtain an approximate classical description of a d-dimensional quantum state when given access to a unitary (and its inverse) that prepares it. For pure states we characterize the query complexity for ℓq-norm error up to logarithmic factors. As a special case, we show that it takes Θ(d/ε) applications of the unitaries to obtain an ε-ℓ2-approximation of the state. For mixed states we consider a similar model, where the unitary prepares a purification of the state. In this model we give an efficient algorithm for obtaining Schatten q-norm estimates of a rank-r mixed state, giving query upper bounds that are close to optimal. In particular, we show that a trace-norm (q=1) estimate can be obtained with O(dr/ε) queries. This improves (assuming our stronger input model) the ε-dependence over the algorithm of Haah et al.\ (2017) that uses a joint measurement on O(dr/ε2) copies of the state. To our knowledge, the most sample-efficient results for pure-state tomography come from setting the rank to 1 in generic mixed-state tomography algorithms, which can be computationally demanding. We describe sample-optimal algorithms for pure states that are easy and fast to implement. Along the way we show that an ℓ∞-norm estimate of a normalized vector induces a (slightly worse) ℓq-norm estimate for that vector, without losing a dimension-dependent factor in the precision. We also develop an unbiased and symmetric version of phase estimation, where the probability distribution of the estimate is centered around the true value. Finally, we give an efficient method for estimating multiple expectation values, improving over the recent result by Huggins et al.\ (2021) when the measurement operators do not fully overlap.
We present a method that outputs a sequence of simple unitary operations to prepare a given quantum state that is a generalized coherent state. Our method takes as inputs the expectation values of some relevant observables. Such expectations can be estimated by performing projective measurements on O(M3log(M/δ)/ε2) copies of the state, where M is the dimension of an associated Lie algebra, ɛ is a precision parameter, and 1 − δ is the required confidence level. The method can be implemented on a classical computer and runs in time O(M4log(M/ε)). It provides O(Mlog(M/ε)) simple unitaries that form the sequence. The overall complexity is then polynomial in M, being very efficient in cases where M is significantly smaller than the Hilbert space dimension, as for some fermion algebras. When the algebra of relevant observables is given by certain Pauli matrices, each simple unitary may be easily decomposed into two-qubit gates. We discuss applications to efficient quantum state tomography and classical simulations of quantum circuits.
Preparing complex quantum states is of limited value without efficient methods for extracting useful classical information from them. This thesis studies when such information can be extracted efficiently, given copies of an unknown quantum state or query access to an unknown unitary transformation. We begin with pure state tomography. We present an algorithm that uses only nonadaptive single-qubit Pauli measurements yet achieves optimal copy and time complexities up to logarithmic factors. This is the first full state tomography algorithm with near-optimal running time. We then show how additional structure can make tomography time-efficient, giving algorithms for two structured classes of quantum states: non-interacting fermions and near-stabilizer states. We also introduce a new learning task, agnostic tomography, where the goal is to find the best approximation to an arbitrary quantum state from a structured class of states, and give efficient algorithms in this model. Turning to property testing, we give an efficient tester for stabilizer dimension, which implies that Ω(n) T-gates are necessary for any Clifford+T circuit to prepare n-qubit computationally pseudorandom states. We also prove copy-complexity lower bounds for testing low-degree phase states, showing that testing is nearly as hard as learning these states. More strongly, for every fixed degree d, ensembles of n-qubit degree-d phase states form exponentially accurate approximate state t-designs for t=Ω(n^{⌊(d-1)/2⌋}). Finally, we extend these questions from states to unitary transformations. We develop a general framework for learning unitary transformations by exploiting low-complexity Pauli spectra. This framework unifies and extends prior learning algorithms for Clifford and near-Clifford circuits, shallow circuits, quantum juntas, and fermionic matchgate circuits.
Quantum state tomography is the problem of estimating a given quantum state. Usually, it is required to run the quantum experiment - state preparation, state evolution, measurement - several times to be able to estimate the output quantum state of the experiment, because an exponentially high number of copies of the state is required. In this work, we present an efficient algorithm to estimate with a small but nonzero probability of error the output state of the experiment using a single copy of the state, without knowing the evolution dynamics of the state. It also does not destroy the original state, which can be recovered easily for any further quantum processing. As an example, it is usually required to repeat a quantum image processing experiment many times, since many copies of the state of the output image are needed to extract the information from all its pixels. The information fromNpixels of the image can be inferred from a single run of the image processing experiment in our algorithm, to efficiently estimate the density matrix of the image state.