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- NSF-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
Single-photon sources are a fundamental resource in quantum optics and quantum information science. Photons with differing spectral and temporal shapes do not interfere well and inhibit the performance of quantum applications such as linear optics quantum computing, boson sampling, and quantum networks. Indistinguishability and purity of photons emitted from different sources are crucial properties for many quantum applications. The ability to determine the state of single-photon sources therefore provides a means to assess their quality, compare different sources, and provide feedback for source tuning. Here, we propose and demonstrate a single-configuration experimental method enabling complete characterization of the spectral-temporal state of a pulsed single-photon source having both pure and mixed states. The method involves interference of the unknown single-photon source with a reference at a balanced beam splitter followed by frequency-resolved coincidence detection at the outputs. Fourier analysis of the joint-spectral two-photon interference pattern reveals the density matrix of the single-photon source in the frequency basis. We present an experimental realization of this method for pure and mixed state pulsed single-photon sources.
-
more » « less
We present an algorithmic framework for quantum-inspired classical algorithms on close-to-low-rank matrices, generalizing the series of results started by Tang’s breakthrough quantum-inspired algorithm for recommendation systems [STOC’19]. Motivated by quantum linear algebra algorithms and the quantum singular value transformation (SVT) framework of Gilyén et al. [STOC’19], we develop classical algorithms for SVT that run in time independent of input dimension, under suitable quantum-inspired sampling assumptions. Our results give compelling evidence that in the corresponding QRAM data structure input model, quantum SVT does not yield exponential quantum speedups. Since the quantum SVT framework generalizes essentially all known techniques for quantum linear algebra, our results, combined with sampling lemmas from previous work, suffice to generalize all prior results about dequantizing quantum machine learning algorithms. In particular, our classical SVT framework recovers and often improves the dequantization results on recommendation systems, principal component analysis, supervised clustering, support vector machines, low-rank regression, and semidefinite program solving. We also give additional dequantization results on low-rank Hamiltonian simulation and discriminant analysis. Our improvements come from identifying the key feature of the quantum-inspired input model that is at the core of all prior quantum-inspired results: ℓ2-norm sampling can approximate matrix products in time independent of their dimension. We reduce all our main results to this fact, making our exposition concise, self-contained, and intuitive.
-
more » « less
Abstract Qudit entanglement is an indispensable resource for quantum information processing since increasing dimensionality provides a pathway to higher capacity and increased noise resilience in quantum communications, and cluster-state quantum computations. In continuous-variable time–frequency entanglement, encoding multiple qubits per photon is only limited by the frequency correlation bandwidth and detection timing jitter. Here, we focus on the discrete-variable time–frequency entanglement in a biphoton frequency comb (BFC), generating by filtering the signal and idler outputs with a fiber Fabry–Pérot cavity with 45.32 GHz free-spectral range (FSR) and 1.56 GHz full-width-at-half-maximum (FWHM) from a continuous-wave (cw)-pumped type-II spontaneous parametric downconverter (SPDC). We generate a BFC whose time-binned/frequency-binned Hilbert space dimensionality is at least 324, based on the assumption of a pure state. Such BFC’s dimensionality doubles up to 648, after combining with its post-selected polarization entanglement, indicating a potential 6.28 bits/photon classical-information capacity. The BFC exhibits recurring Hong–Ou–Mandel (HOM) dips over 61 time bins with a maximum visibility of 98.4% without correction for accidental coincidences. In a post-selected measurement, it violates the Clauser–Horne–Shimony–Holt (CHSH) inequality for polarization entanglement by up to 18.5 standard deviations with an
S -parameter of up to 2.771. It has Franson interference recurrences in 16 time bins with a maximum visibility of 96.1% without correction for accidental coincidences. From the zeroth- to the third-order Franson interference, we infer an entanglement of formation (E of) up to 1.89 ± 0.03 ebits—where 2 ebits is the maximal entanglement for a 4 × 4 dimensional biphoton—as a lower bound on the 61 time-bin BFC’s high-dimensional entanglement. To further characterize time-binned/frequency-binned BFCs we obtain Schmidt mode decompositions of BFCs generated using cavities with 45.32, 15.15, and 5.03 GHz FSRs. These decompositions confirm the time–frequency scaling from Fourier-transform duality. Moreover, we present the theory of conjugate Franson interferometry—because it is characterized by the state’s joint-temporal intensity (JTI)—which can further help to distinguish between pure-state BFC and mixed state entangled frequency pairs, although the experimental implementation is challenging and not yet available. In summary, our BFC serves as a platform for high-dimensional quantum information processing and high-dimensional quantum key distribution (QKD). -
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
