We give two new quantum algorithms for solving semidefinite programs (SDPs) providing quantum speed-ups. We consider SDP instances with m constraint matrices, each of dimension n, rank at most r, and sparsity s. The first algorithm assumes an input model where one is given access to an oracle to the entries of the matrices at unit cost. We show that it has run time O~(s^2 (sqrt{m} epsilon^{-10} + sqrt{n} epsilon^{-12})), with epsilon the error of the solution. This gives an optimal dependence in terms of m, n and quadratic improvement over previous quantum algorithms (when m ~~ n). The second algorithm assumes a fully quantum input model in which the input matrices are given as quantum states. We show that its run time is O~(sqrt{m}+poly(r))*poly(log m,log n,B,epsilon^{-1}), with B an upper bound on the trace-norm of all input matrices. In particular the complexity depends only polylogarithmically in n and polynomially in r. We apply the second SDP solver to learn a good description of a quantum state with respect to a set of measurements: Given m measurements and a supply of copies of an unknown state rho with rank at most r, we show we can find in time sqrt{m}*poly(log m,log n,r,epsilon^{-1}) a description of the state as a quantum circuit preparing a density matrix which has the same expectation values as rho on the m measurements, up to error epsilon. The density matrix obtained is an approximation to the maximum entropy state consistent with the measurement data considered in Jaynes' principle from statistical mechanics. As in previous work, we obtain our algorithm by "quantizing" classical SDP solvers based on the matrix multiplicative weight update method. One of our main technical contributions is a quantum Gibbs state sampler for low-rank Hamiltonians, given quantum states encoding these Hamiltonians, with a poly-logarithmic dependence on its dimension, which is based on ideas developed in quantum principal component analysis. We also develop a "fast" quantum OR lemma with a quadratic improvement in gate complexity over the construction of Harrow et al. [Harrow et al., 2017]. We believe both techniques might be of independent interest.
more »
« less
Quantum mixed state compiling
The task of learning a quantum circuit to prepare a given mixed state is a fundamental quantum subroutine. We present a variational quantum algorithm (VQA) to learn mixed states which is suitable for near-term hardware. Our algorithm represents a generalization of previous VQAs that aimed at learning preparation circuits for pure states. We consider two different ansätze for compiling the target state; the first is based on learning a purification of the state and the second on representing it as a convex combination of pure states. In both cases, the resources required to store and manipulate the compiled state grow with the rank of the approximation. Thus, by learning a lower rank approximation of the target state, our algorithm provides a means of compressing a state for more efficient processing. As a byproduct of our algorithm, one effectively learns the principal components of the target state, and hence our algorithm further provides a new method for principal component analysis. We investigate the efficacy of our algorithm through extensive numerical implementations, showing that typical random states and thermal states of many body systems may be learnt this way. Additionally, we demonstrate on quantum hardware how our algorithm can be used to study hardware noise-induced states.
more » « less- PAR ID:
- 10405216
- Publisher / Repository:
- IOP Publishing
- Date Published:
- Journal Name:
- Quantum Science and Technology
- Volume:
- 8
- Issue:
- 3
- ISSN:
- 2058-9565
- Page Range / eLocation ID:
- Article No. 035001
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
more » « less
Security and reliability are primary concerns in any computing paradigm, including quantum computing. Currently, users can access quantum computers through a cloud-based platform where they can run their programs on a suite of quantum computers. As the quantum computing ecosystem grows in popularity and utility, it is reasonable to expect that more companies including untrusted/less-trusted/unreliable vendors will begin offering quantum computers as hardware-as-a-service at varied price/performance points. Since computing time on quantum hardware is expensive and the access queue could be long, the users will be motivated to use the cheaper and readily available but unreliable/less-trusted hardware. The less-trusted vendors can tamper with the results, providing a sub-optimal solution to the user. For applications such as, critical infrastructure optimization, the inferior solution may have significant socio-political implications. Since quantum computers cannot be simulated in classical computers, users have no way of verifying the computation outcome. In this paper, we address this challenge by modeling adversarial tampering and simulating it's impact on both pure quantum and hybrid quantum-classical workloads. To achieve trustworthy computing in a mixed environment of trusted and untrusted hardware, we propose an equitable distribution of total shots (i.e., repeated executions of quantum programs) across hardware options. On average, we note ≈ 30X and ≈ 1.5X improvement across the pure quantum workloads and a maximum improvement of ≈ 5X for hybrid-classical algorithm in the chosen quality metrics. We also propose an intelligent run adaptive shot distribution heuristic leveraging temporal variation in hardware quality to user's advantage, allowing them to identify tampered/untrustworthy hardware at runtime and allocate more number of shots to the reliable hardware, which results in a maximum improvement of ≈ 190X and ≈ 9X across the pure quantum workloads and an improvement of up to ≈ 2.5X for hybrid-classical algorithm.
-
It has been recently shown that a state generated by a one-dimensional noisy quantum computer is well approximated by a matrix product operator with a finite bond dimension independent of the number of qubits. We show that full quantum state tomography can be performed for such a state with a minimal number of measurement settings using a method known as tensor train cross approximation. The method works for reconstructing full rank density matrices and only requires measuring local operators, which are routinely performed in state-of-art experimental quantum platforms. Our method requires exponentially fewer state copies than the best known tomography method for unstructured states and local measurements. The fidelity of our reconstructed state can be further improved via supervised machine learning, without demanding more experimental data. Scalable tomography is achieved if the full state can be reconstructed from local reductions.more » « less
-
more » « less
Abstract Quantum systems have entered a competitive regime in which classical computers must make approximations to represent highly entangled quantum states1,2. However, in this beyond-classically-exact regime, fidelity comparisons between quantum and classical systems have so far been limited to digital quantum devices2–5, and it remains unsolved how to estimate the actual entanglement content of experiments6. Here, we perform fidelity benchmarking and mixed-state entanglement estimation with a 60-atom analogue Rydberg quantum simulator, reaching a high-entanglement entropy regime in which exact classical simulation becomes impractical. Our benchmarking protocol involves extrapolation from comparisons against an approximate classical algorithm, introduced here, with varying entanglement limits. We then develop and demonstrate an estimator of the experimental mixed-state entanglement6, finding our experiment is competitive with state-of-the-art digital quantum devices performing random circuit evolution2–5. Finally, we compare the experimental fidelity against that achieved by various approximate classical algorithms, and find that only the algorithm we introduce is able to keep pace with the experiment on the classical hardware we use. Our results enable a new model for evaluating the ability of both analogue and digital quantum devices to generate entanglement in the beyond-classically-exact regime, and highlight the evolving divide between quantum and classical systems.
-
more » « less
We study quantum many-body mixed states with a symmetry from the perspective of , i.e., whether a mixed state can be expressed as an ensemble of short-range-entangled symmetric pure states. We provide evidence for “symmetry-enforced separability transitions” in a variety of states, where in one regime the mixed state is expressible as a convex sum of symmetric short-range-entangled pure states, while in the other regime, such a representation is not feasible. We first discuss the Gibbs state of Hamiltonians that exhibit spontaneous breaking of a discrete symmetry, and argue that the associated thermal phase transition can be thought of as a symmetry-enforced separability transition. Next we study cluster states in various dimensions subjected to local decoherence, and identify several distinct mixed-state phases and associated separability phase transitions, which also provides an alternative perspective on recently discussed “average symmetry-protected topological order.” We also study decoheredsuperconductors, and find that if the decoherence breaks the fermion parity explicitly, then the resulting mixed state can be expressed as a convex sum of nonchiral states, while a fermion parity–preserving decoherence results in a phase transition at a nonzero threshold that corresponds to spontaneous breaking of fermion parity. Finally, we briefly discuss systems that satisfy the no low-energy trivial state property, such as the recently discovered good low-density parity-check codes, and argue that the Gibbs state of such systems exhibits a temperature-tuned separability transition.
Published by the American Physical Society 2024
