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 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 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.
The subject of this thesis, quantum estimation theory, is inspired by recent developments, both practical and theoretical, in the new field of quantum information and computation. The main task of quantum estimation theory, the subject of this thesis, is that given many identical copies of an unknown quantum system one wants to guess or estimate what the system is. This is done by performing an measurement and analyzing the data obtained from it.
A quantum state is represented by a density matrix. In some cases one does not need to know the whole density matrix, sometimes a partial characterization is enough. Chapter 2 of this thesis is about optimally estimating the spectrum, i.e. the eigenvalues, of a density matrix. This is useful, for example, for estimating the entanglement of a bipartite pure state. The results of chapter 2 tell us that one can optimally estimate bipartite entanglement with LOCC measurements on one of the two parties.
Unitary operations transform density matrices to density matrices. They are the gates of quantum information processing. Suppose one has one such unitary operation but one does not know what it does. In order to characterize it one needs to know how it transforms any input state. In order to know how a particular state is transformed, one can prepare that state, feed it to the unitary many times, and measure the output. One state is, of course, not enough. It turns out that the unitary can be completely characterized with a finite set of states, this is known as quantum process tomography. Unfortunately, in many cases it is difficult to have available in the lab all the input states needed to perform quantum process tomography. It is here where entanglement comes to the rescue. One pair of maximally entangled qubits, where one of them is used as input for the unitary gate and the other is left untouched, is sufficient. All the information about the unknown gate is contained in the joint output state. This is the problem treated in chapter 3. Now the output state needs to be measured. Again, one could measure the two qubits separately (LOCC) or jointly (collective measurement). Is there anything to gain by performing joint measurements? The answer is yes, optimal collective measurements are at least 3 times more accurate than any LOCC measurement.
Chapter 4 treats the problem of estimating commuting unitary gates. There it is shown that this extra information makes it unnecessary to use an entangled input state and to use collective measurements at the output.
In chapters 3 and 4 it is assumed that only one copy of the unitary gate is available. If, however, more than one copy (say N ) are available at the same time one could use an N-fold entangled state as input. If no entanglement is used, classical statistics tells us that the error of the estimation is proportional to 1/√N. In the literature, it has been shown that by using an entangled state in the input one can achieve an error proportional to 1/N. However, this has been shown only for qubit gates. In chapter 5 important steps are taken in the direction of showing the same thing for a general unitary gate, but this remains an open problem.
We consider performing phase estimation under the following conditions: we are given only one copy of the input state, the input state does not have to be an eigenstate of the unitary, and the state must not be measured. Most quantum estimation algorithms make assumptions that make them unsuitable for this 'coherent' setting, leaving only the textbook approach. We present novel algorithms for phase, energy, and amplitude estimation that are both conceptually and computationally simpler than the textbook method, featuring both a smaller query complexity and ancilla footprint. They do not require a quantum Fourier transform, and they do not require a quantum sorting network to compute the median of several estimates. Instead, they use block-encoding techniques to compute the estimate one bit at a time, performing all amplification via singular value transformation. These improved subroutines accelerate the performance of quantum Metropolis sampling and quantum Bayesian inference.
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
Quantum process tomography (QPT) methods aim at identifying a given quantum process. QPT is a major quantum information processing tool, since it especially allows one to characterize the actual behavior of quantum gates, which are the building blocks of quantum computers. The present paper focuses on the estimation of a unitary process. This class is of particular interest because quantum mechanics postulates that the evolution of any closed quantum system is described by a unitary transformation. Unitary processes have significantly fewer parameters than general quantum processes (22nqb vs. 24nqb−22nqb real independent parameters for nqb qubits). By assuming that the process is unitary we develop two methods that scale better with the size of the system. In the present paper, we stay as close as possible to the standard setup of QPT: the operator has to prepare copies of different input states. The properties those states have to satisfy in order for our method to achieve QPT are very mild. Therefore, we choose to operate with copies of 2nqb initially unknown pure input states. In order to perform QPT without knowing the input states, we perform measurements on half the copies of each state, and let the other half be transformed by the system before measuring them (each copy is only measured once). This setup has the advantage of removing the issue of systematic (i.e., same on all the copies of a state) errors entirely because it does not require the process input to take predefined values. We develop a straightforward analytical solution that first estimates the states from the averaged measurements and then finds the unitary matrix (representing the process) coherent with those estimates by using our analytical solution to an extended version of Wahba’s problem. This estimate may then be used as an initial point for a fine tuning algorithm that maximizes the likelihood of the measurements. Simulation results show the effectiveness of the proposed methods.
We describe a procedure that simultaneously reduces the dimensions of many, potentially distinct quantum states while preserving properties invariant under the tensor power action of an isometry. This serves as a black-box method to replace the dimension with the maximum rank in the sample complexity of learning symmetric properties, even those depending on multiple input states. Combined with full state tomography, random dimension reduction yields improved upper bounds for estimating distances, fidelities, and relative entropies between pairs of states.
Expressing the action of this procedure through the Choi--Jamiołkowski isomorphism reveals an intimate connection with the recently introduced random purification channel by Tang, Wright, and Zhandry. With this new perspective, we obtain a simple description of the rank-dependent version of the random purification channel and give an end-to-end analysis of sample-optimal tomography without requiring a reference to the Schur transform or Schur polynomials. Finally, we prove that there does not exist a random purification channel that simultaneously purifies copies of multiple, potentially different input states. Hence, the procedure is related to, but distinct from, random purification.