Second order cone relaxations for quantum Max Cut

• URL: http://arxiv.org/abs/2411.04120v1
• Date: Wed, 06 Nov 2024 18:54:26 GMT
• Title: Second order cone relaxations for quantum Max Cut
• Authors: Felix Huber, Kevin Thompson, Ojas Parekh, Sevag Gharibian,
• Abstract summary: Quantum Max Cut (QMC) is a QMA-complete problem relevant to quantum many-body physics and computer science. We give a second order cone relaxation for QMC, which optimize over the set of mutually consistent three-qubit reduced density matrices. Our relaxation is solvable on systems with hundreds of qubits and paves the way to computationally efficient lower and upper bounds on the ground state energy of large-scale quantum spin systems.
• Score: 3.237380113935023
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quantum Max Cut (QMC), also known as the quantum anti-ferromagnetic Heisenberg model, is a QMA-complete problem relevant to quantum many-body physics and computer science. Semidefinite programming relaxations have been fruitful in designing theoretical approximation algorithms for QMC, but are computationally expensive for systems beyond tens of qubits. We give a second order cone relaxation for QMC, which optimizes over the set of mutually consistent three-qubit reduced density matrices. In combination with Pauli level-$1$ of the quantum Lasserre hierarchy, the relaxation achieves an approximation ratio of $0.526$ to the ground state energy. Our relaxation is solvable on systems with hundreds of qubits and paves the way to computationally efficient lower and upper bounds on the ground state energy of large-scale quantum spin systems.

Related papers

• A Quantum Approximate Optimization Algorithm for Local Hamiltonian Problems [0.0]
  Local Hamiltonian Problems (LHPs) are important problems that are computationally-complete and physically relevant for many-body quantum systems. We propose and analyze a quantum approximation which we call the Hamiltonian Quantum Approximate Optimization Algorithm (HamQAOA) Our results indicate that the linear-depth HamQAOA can deterministically prepare exact ground states of 1-dimensional antiferromagnetic Heisenberg spin chains.
  arXiv  Detail & Related papers  (2024-12-12T12:22:08Z)
• Spin coupling is all you need: Encoding strong electron correlation on quantum computers [0.0]
  We show that quantum computers can efficiently simulate strongly correlated molecular systems by directly encoding the dominant entanglement structure in the form of spin-coupled initial states. Our work paves the way towards scalable quantum simulation of electronic structure for classically challenging systems.
  arXiv  Detail & Related papers  (2024-04-29T17:14:21Z)
• A Quantum-Classical Collaborative Training Architecture Based on Quantum State Fidelity [50.387179833629254]
  We introduce a collaborative classical-quantum architecture called co-TenQu. Co-TenQu enhances a classical deep neural network by up to 41.72% in a fair setting. It outperforms other quantum-based methods by up to 1.9 times and achieves similar accuracy while utilizing 70.59% fewer qubits.
  arXiv  Detail & Related papers  (2024-02-23T14:09:41Z)
• Evaluating Ground State Energies of Chemical Systems with Low-Depth Quantum Circuits and High Accuracy [6.81054341190257]
  We develop an enhanced Variational Quantum Eigensolver (VQE) ansatz based on the Qubit Coupled Cluster (QCC) approach. We evaluate our enhanced QCC ansatz on two distinct quantum hardware, IBM Kolkata and Quantinuum H1-1.
  arXiv  Detail & Related papers  (2024-02-21T17:45:03Z)
• Quantum computing quantum Monte Carlo with hybrid tensor network for electronic structure calculations [3.642843803494657]
  We propose an algorithm combining QC-QMC with a hybrid tensor network to extend the applicability of QC-QMC beyond a single quantum device size. Our algorithm is evaluated on the Heisenberg chain model, graphite-based Hubbard model, hydrogen plane model, and MonoArylBiImidazole using full configuration interaction QMC.
  arXiv  Detail & Related papers  (2023-03-31T14:38:40Z)
• Quantum Computing Quantum Monte Carlo [8.69884453265578]
  We propose a hybrid quantum-classical algorithm that integrates quantum computing and quantum Monte Carlo. Our work paves the way to solving practical problems with intermediatescale and early-fault tolerant quantum computers.
  arXiv  Detail & Related papers  (2022-06-21T14:26:24Z)
• Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture [0.0]
  We show that the Quantum Singular Value Transformation can be efficiently "dequantized" We show that with inverse-polynomial precision, the same problem becomes BQP-complete. We also discuss how this dequantization technique may help make progress on the central quantum PCP.
  arXiv  Detail & Related papers  (2021-11-17T12:50:13Z)
• An Algebraic Quantum Circuit Compression Algorithm for Hamiltonian Simulation [55.41644538483948]
  Current generation noisy intermediate-scale quantum (NISQ) computers are severely limited in chip size and error rates. We derive localized circuit transformations to efficiently compress quantum circuits for simulation of certain spin Hamiltonians known as free fermions. The proposed numerical circuit compression algorithm behaves backward stable and scales cubically in the number of spins enabling circuit synthesis beyond $mathcalO(103)$ spins.
  arXiv  Detail & Related papers  (2021-08-06T19:38:03Z)
• Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
  We introduce a high-fidelity gate set inspired by a proposal for near-term quantum advantage in optimization problems. By orchestrating coherent, multi-level control over three transmon qutrits, we synthesize a family of deterministic, continuous-angle quantum phase gates acting in the natural three-qubit computational basis.
  arXiv  Detail & Related papers  (2021-08-03T17:49:09Z)
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
  Matching problems on 3D shapes and images are frequently formulated as quadratic assignment problems (QAPs) with permutation matrix constraints, which are NP-hard. We propose several reformulations of QAPs as unconstrained problems suitable for efficient execution on quantum hardware. The proposed algorithm has the potential to scale to higher dimensions on future quantum computing architectures.
  arXiv  Detail & Related papers  (2021-07-08T17:59:55Z)
• Error mitigation and quantum-assisted simulation in the error corrected regime [77.34726150561087]
  A standard approach to quantum computing is based on the idea of promoting a classically simulable and fault-tolerant set of operations. We show how the addition of noisy magic resources allows one to boost classical quasiprobability simulations of a quantum circuit.
  arXiv  Detail & Related papers  (2021-03-12T20:58:41Z)
• Simulation of Thermal Relaxation in Spin Chemistry Systems on a Quantum Computer Using Inherent Qubit Decoherence [53.20999552522241]
  We seek to take advantage of qubit decoherence as a resource in simulating the behavior of real world quantum systems. We present three methods for implementing the thermal relaxation. We find excellent agreement between our results, experimental data, and the theoretical prediction.
  arXiv  Detail & Related papers  (2020-01-03T11:48:11Z)

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.