A fundamental task in quantum information is to approximate a pure quantum state in terms of sparse states or, for a bipartite system, states of bounded Schmidt rank. The optimal deterministic approximation in each case is straightforward, and maximizes the fidelity: keep the largest entries or singular values. On the other hand, random mixtures of sparse states can achieve quadratically improved trace distances, and yield nontrivial bounds on other distance measures like the robustness. In this work, we give efficient algorithms for finding mixtures of sparse states that optimally approximate a given pure state in either trace distance or robustness. These algorithms also yield descriptions of efficiently samplable ensembles of sparse, or less-entangled, states that correspond to these optimal mixed approximations. This can be used for the truncation step of algorithms for matrix product states, improving their accuracy while using no extra memory and no asymptotic increase in runtime, and we demonstrate this improvement numerically. Our proofs rely on tools from convex optimization and zero-sum games, as well as rigorous gurarantees for computing and sampling from maximum-entropy distributions. In particular, a key step in our construction is conditional Poisson sampling, which is the well-studied problem of drawing fixed-size subsets from a population with known inclusion probabilities. We give improved algorithms for carrying out this sampling, which may be of independent interest.
A fundamental task in quantum information is to approximate a pure quantum state in terms of sparse states or, for a bipartite system, states of bounded Schmidt rank. The optimal deterministic approximation in each case is straightforward, and maximizes the fidelity: keep the largest entries or singular values. On the other hand, random mixtures of sparse states can achieve quadratically improved trace distances, and yield nontrivial bounds on other distance measures like the robustness. In this work, we give efficient algorithms for finding mixtures of sparse states that optimally approximate a given pure state in either trace distance or robustness. These algorithms also yield descriptions of efficiently samplable ensembles of sparse, or less-entangled, states that correspond to these optimal mixed approximations. This can be used for the truncation step of algorithms for matrix product states, improving their accuracy while using no extra memory and no asymptotic increase in runtime, and we demonstrate this improvement numerically. Our proofs rely on tools from convex optimization and zero-sum games, as well as rigorous gurarantees for computing and sampling from maximum-entropy distributions. In particular, a key step in our construction is conditional Poisson sampling, which is the well-studied problem of drawing fixed-size subsets from a population with known inclusion probabilities. We give improved algorithms for carrying out this sampling, which may be of independent interest.
We study the problem of tomography for k-sparse quantum states. In contrast to classical distribution learning, where tight sample and time complexity bounds in terms of support size are well understood, no non-trivial bounds were previously shown for this problem. We give the first near optimal algorithm for learning n-qubit k-sparse pure quantum states, obtaining fidelity at least 1−ε with high probability using O~(k/ε) copies of the state and O~(kn/ε) time. Both bounds are optimal up to polylogarithmic factors. As an implication, we also obtain an algorithm with near optimal O~(kr/ε) sample complexity for learning k-sparse rank-r mixed states, via the random purification channel technique. Obtaining time complexity nearly matching the sample complexity, for r>1, remains an important open question.
Fidelity is a fundamental measure for the closeness of two quantum states, which is important both from a theoretical and a practical point of view. Yet, in general, it is difficult to give good estimates of fidelity, especially when one works with mixed states over Hilbert spaces of very high dimension. Although, there has been some progress on fidelity estimation, all prior work either requires a large number of identical copies of the relevant states, or relies on unproven heuristics. In this work, we improve on both of these aspects by developing new and efficient quantum algorithms for fidelity estimation with provable performance guarantees in case at least one of the states is approximately low-rank. Our algorithms use advanced quantum linear algebra techniques, such as the quantum singular value transformation, as well as density matrix exponentiation and quantum spectral sampling. As a complementary result, we prove that fidelity estimation to any non-trivial constant additive accuracy is hard in general, by giving a sample complexity lower bound that depends polynomially on the dimension. Moreover, if circuit descriptions for the relevant states are provided, we show that the task is hard for the complexity class called (honest verifier) quantum statistical zero knowledge via a reduction to a closely related result by Watrous.
Pure quantum states are often approximately encoded as classical bit strings such as those representing probability amplitudes and those describing circuits that generate the quantum states. The crucial quantity is the minimum length of classical bit strings from which the original pure states are approximately reconstructible. We derive asymptotically tight bounds on the minimum bit length required for probabilistic encodings with which one can approximately reconstruct the original pure state as an ensemble of the quantum states encoded in classical strings. We also show that such a probabilistic encoding asymptotically halves the bit length required for "deterministic" ones. This is based on the fact that the accuracy of approximating pure states by using a given subset of pure states can be increased quadratically if we use ensembles of pure states in the subset. Moreover, we show that a similar fact holds when we consider the approximation of unitary gates by using a given subset of unitary gates. This improves the reduction rate of the circuit size by using probabilistic circuit synthesis compared to previous results. This also demonstrates that the reduction is possible even for low-accuracy circuit synthesis, which might improve the accuracy of various NISQ algorithms.
The optimal (pure state) ensemble length of a separable state, A, is the minimum number of (pure) product states needed in convex combination to construct A. We study the set of all separable states with optimal (pure state) ensemble length equal to k or fewer. Lower bounds on k are found below which these sets have measure 0 in the set of separable states. In the bipartite case and the multiparticle case where one of the particles has significantly more quantum numbers than the rest, the lower bounds are sharp. A consequence of our results is that for all two particle systems, except possibly those with a qubit and those with a nine dimensional Hilbert space, and for all systems with more than two particles the optimal pure state ensemble length for a randomly picked separable state is with probability 1 greater than the state’s rank. In bipartite systems with each particle having the same Hilbert space, with probablity 1 it is greater than 1/4 the rank raised to the 3/2 power and in a system with p qubits with probability 1 it is greater than 2 2p /(1 + 2p), which is almost the maximal rank squared. 1
The preparation of quantum states is one of the most fundamental tasks in quantum computing, and a key primitive in many quantum algorithms. Of particular interest to areas such as quantum simulation and linear-system solvers are sparse quantum states, which contain only a small number s of non-zero computational basis states compared to a generic state. In this work, we present an approach that prepares s-sparse states on n qubits, reducing the number of Toffoli gates required compared to prior art. We work in the established framework of first preparing a dense state on a ⌈log(s)⌉-qubit sub-register, and then mapping this state to the target state via an isometry, with the latter step dominating the cost of the full algorithm. The speed-up is achieved by designing an efficient algorithm for finding and implementing the isometry. The worst-case Toffoli cost of our isometry circuit, which may be viewed as a batched version of an approach by Malvetti et al., is essentially 2s for sufficiently large values of n, yielding roughly a log(s)/2 improvement factor over the state-of-the-art. In numerical benchmarks on randomly chosen states, the cost is closer to s. With the improved isometry circuit, we examine the dense-state preparation step and present ways to optimize the joint cost of both steps, particularly in the case of target states with purely real coefficients, by outsourcing some sub-tasks from the dense-state preparation to the isometry.
Several quantum algorithms for linear algebra problems, and in particular quantum machine learning problems, have been “dequantized” in the past few years. These dequantization results typically hold when classical algorithms can access the data via length-squared sampling. This assumption, which is standard in the field of randomized linear algebra, means that for a unit-norm vector u∈Cn , we can sample from the distribution pu:{1,…,n}→[0,1] defined as pu(i)=∣u(i)∣2 for each i∈{1,…,n} . Since this distribution corresponds to the distribution obtained by measuring the quantum state | u > in the computational basis, length-squared sampling access gives a reasonable classical analogue to the kind of quantum access considered in many quantum algorithms for linear algebra problems. In this work we investigate how robust these dequantization results are. We introduce the notion of approximate length-squared sampling, where classical algorithms are only able to sample from a distribution close to the ideal distribution in total variation distance. While quantum algorithms are natively robust against small perturbations, current techniques in dequantization are not. Our main technical contribution is showing how many techniques from randomized linear algebra can be adapted to work under this weaker assumption as well. We then use these techniques to show that the recent low-rank dequantization framework by Chia, Gilyén, Li, Lin, Tang and Wang (JACM 2022) and the dequantization framework for sparse matrices by Gharibian and Le Gall (STOC 2022), which are both based on the Quantum Singular Value Transformation, can be generalized to the case of approximate length-squared sampling access to the input. We also apply these results to obtain a robust dequantization of many quantum machine learning algorithms, including quantum algorithms for recommendation systems, supervised clustering and low-rank matrix inversion.