Quantum Semidefinite Programming with Thermal Pure Quantum States

• URL: http://arxiv.org/abs/2310.07774v1
• Date: Wed, 11 Oct 2023 18:00:53 GMT
• Title: Quantum Semidefinite Programming with Thermal Pure Quantum States
• Authors: Oscar Watts, Yuta Kikuchi, Luuk Coopmans
• Abstract summary: We show that a quantization'' of the matrix multiplicative-weight algorithm can provide approximate solutions to SDPs quadratically faster than the best classical algorithms. We propose a modification of this quantum algorithm and show that a similar speedup can be obtained by replacing the Gibbs-state sampler with the preparation of thermal pure quantum (TPQ) states.
• Score: 0.5639904484784125
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Semidefinite programs (SDPs) are a particular class of convex optimization problems with applications in combinatorial optimization, operational research, and quantum information science. Seminal work by Brand\~{a}o and Svore shows that a ``quantization'' of the matrix multiplicative-weight algorithm can provide approximate solutions to SDPs quadratically faster than the best classical algorithms by using a quantum computer as a Gibbs-state sampler. We propose a modification of this quantum algorithm and show that a similar speedup can be obtained by replacing the Gibbs-state sampler with the preparation of thermal pure quantum (TPQ) states. While our methodology incurs an additional problem-dependent error, which decreases as the problem size grows, it avoids the preparation of purified Gibbs states, potentially saving a number of ancilla qubits. In addition, we identify a spectral condition which, when met, reduces the resources further, and shifts the computational bottleneck from Gibbs state preparation to ground-state energy estimation. With classical state-vector simulations, we verify the efficiency of the algorithm for particular cases of Hamiltonian learning problems. We are able to obtain approximate solutions for two-dimensional spinless Hubbard and one-dimensional Heisenberg XXZ models for sizes of up to $N=2^{10}$ variables. For the Hubbard model, we provide an estimate of the resource requirements of our algorithm, including the number of Toffoli gates and the number of qubits.

Related papers

• Bias-field digitized counterdiabatic quantum optimization [39.58317527488534]
  We call this protocol bias-field digitizeddiabatic quantum optimization (BF-DCQO) Our purely quantum approach eliminates the dependency on classical variational quantum algorithms. It achieves scaling improvements in ground state success probabilities, increasing by up to two orders of magnitude.
  arXiv  Detail & Related papers  (2024-05-22T18:11:42Z)
• A Universal Quantum Algorithm for Weighted Maximum Cut and Ising Problems [0.0]
  We propose a hybrid quantum-classical algorithm to compute approximate solutions of binary problems. We employ a shallow-depth quantum circuit to implement a unitary and Hermitian operator that block-encodes the weighted maximum cut or the Ising Hamiltonian. Measuring the expectation of this operator on a variational quantum state yields the variational energy of the quantum system.
  arXiv  Detail & Related papers  (2023-06-10T23:28:13Z)
• Efficient MILP Decomposition in Quantum Computing for ReLU Network Robustness [2.854196251981274]
  In this study, we examine two decomposition methods for Mixed-Integer Linear Programming (MILP) We concentrate on breaking down the original problem into smaller subproblems, which are then solved iteratively using a combined quantum-classical hardware approach. Our experimental results demonstrate that this approach can save up to 90% of qubits compared to existing methods on quantum annealing and gate-based quantum computers.
  arXiv  Detail & Related papers  (2023-04-30T13:10:56Z)
• Solving Graph Problems Using Gaussian Boson Sampling [22.516585968074146]
  We use a noisy intermediate-scale quantum computer to solve graph problems. We experimentally observe the presence of GBS enhancement with large photon-click number and an enhancement under certain noise. Our work is a step toward testing real-world problems using the existing intermediate-scale quantum computers.
  arXiv  Detail & Related papers  (2023-02-02T08:25:47Z)
• Analyzing Prospects for Quantum Advantage in Topological Data Analysis [35.423446067065576]
  We analyze and optimize an improved quantum algorithm for topological data analysis. We show that super-quadratic quantum speedups are only possible when targeting a multiplicative error approximation. We argue that quantum circuits with tens of billions of Toffoli can solve seemingly classically intractable instances.
  arXiv  Detail & Related papers  (2022-09-27T17:56:15Z)
• Provably efficient variational generative modeling of quantum many-body systems via quantum-probabilistic information geometry [3.5097082077065003]
  We introduce a generalization of quantum natural gradient descent to parameterized mixed states. We also provide a robust first-order approximating algorithm, Quantum-Probabilistic Mirror Descent. Our approaches extend previously sample-efficient techniques to allow for flexibility in model choice.
  arXiv  Detail & Related papers  (2022-06-09T17:58:15Z)
• Quantum Speedup for Higher-Order Unconstrained Binary Optimization and MIMO Maximum Likelihood Detection [2.5272389610447856]
  We propose a quantum algorithm that supports a real-valued higher-order unconstrained binary optimization problem. The proposed algorithm is capable of reducing the query complexity in the classical domain and providing a quadratic speedup in the quantum domain.
  arXiv  Detail & Related papers  (2022-05-31T00:14:49Z)
• Adaptive variational algorithms for quantum Gibbs state preparation [0.0]
  We introduce an objective function that, unlike the free energy, is easily measured, and (ii) using dynamically generated, problem-tailored ans"atze. This allows for arbitrarily accurate Gibbs state preparation using low-depth circuits. We numerically demonstrate that our algorithm can prepare high-fidelity Gibbs states across a broad range of temperatures and for a variety of Hamiltonians.
  arXiv  Detail & Related papers  (2022-03-23T22:54:19Z)
• Quantum algorithms for grid-based variational time evolution [36.136619420474766]
  We propose a variational quantum algorithm for performing quantum dynamics in first quantization. Our simulations exhibit the previously observed numerical instabilities of variational time propagation approaches.
  arXiv  Detail & Related papers  (2022-03-04T19:00:45Z)
• Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays [39.76254807200083]
  We experimentally investigate quantum algorithms for solving the Maximum Independent Set problem. We find the problem hardness is controlled by the solution degeneracy and number of local minima. On the hardest graphs, we observe a superlinear quantum speedup in finding exact solutions.
  arXiv  Detail & Related papers  (2022-02-18T19:00:01Z)
• Bosonic field digitization for quantum computers [62.997667081978825]
  We address the representation of lattice bosonic fields in a discretized field amplitude basis. We develop methods to predict error scaling and present efficient qubit implementation strategies.
  arXiv  Detail & Related papers  (2021-08-24T15:30:04Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.