Expanding the reach of quantum optimization with fermionic embeddings
- URL: http://arxiv.org/abs/2301.01778v2
- Date: Fri, 9 Jun 2023 22:12:05 GMT
- Title: Expanding the reach of quantum optimization with fermionic embeddings
- Authors: Andrew Zhao, Nicholas C. Rubin
- Abstract summary: We study a class of hard optimization problems that do not have an efficient quantum representation.
The embedded LNCG Hamiltonian is a two-body fermion model.
We provide evidence that this rounded quantum relaxation can produce high-quality approximations.
- Score: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Quadratic programming over orthogonal matrices encompasses a broad class of
hard optimization problems that do not have an efficient quantum
representation. Such problems are instances of the little noncommutative
Grothendieck problem (LNCG), a generalization of binary quadratic programs to
continuous, noncommutative variables. In this work, we establish a natural
embedding for this class of LNCG problems onto a fermionic Hamiltonian, thereby
enabling the study of this classical problem with the tools of quantum
information. This embedding is accomplished by identifying the orthogonal group
with its double cover, which can be represented as fermionic quantum states.
Correspondingly, the embedded LNCG Hamiltonian is a two-body fermion model.
Determining extremal states of this Hamiltonian provides an outer approximation
to the original problem, a quantum analogue to classical semidefinite
relaxations. In particular, when optimizing over the special orthogonal group
our quantum relaxation obeys additional, powerful constraints based on the
convex hull of rotation matrices. The classical size of this convex-hull
representation is exponential in matrix dimension, whereas our quantum
representation requires only a linear number of qubits. Finally, to project the
relaxed solution back into the feasible space, we propose rounding procedures
which return orthogonal matrices from appropriate measurements of the quantum
state. Through numerical experiments we provide evidence that this rounded
quantum relaxation can produce high-quality approximations.
Related papers
- Unleashed from Constrained Optimization: Quantum Computing for Quantum
Chemistry Employing Generator Coordinate Method [10.6794560287257]
Hybrid quantum-classical approaches offer potential solutions for quantum chemistry problems.
But they also introduce challenges such as the barren plateau and the exactness of the ansatze.
In this work, we highlight the interconnection between constrained optimization and generalized eigenvalue problems.
arXiv Detail & Related papers (2023-12-12T19:36:51Z) - Analysis of sum-of-squares relaxations for the quantum rotor model [0.0]
The noncommutative sum-of-squares hierarchy was introduced by Navascu'es-Pironio-Ac'i as a sequence of semidefinite programming relaxations for approximating quantum values of nonlocal games.
Recent work has started to analyze the hierarchy for approximating ground energies of local Hamiltonians.
arXiv Detail & Related papers (2023-11-15T14:53:22Z) - Gelfand-Tsetlin basis for partially transposed permutations, with
applications to quantum information [0.9208007322096533]
We study representation theory of the partially transposed permutation matrix algebra.
We show how to simplify semidefinite optimization problems over unitary-equivariant quantum channels.
We derive an efficient quantum circuit for implementing the optimal port-based quantum teleportation protocol.
arXiv Detail & Related papers (2023-10-03T17:55:10Z) - Vectorization of the density matrix and quantum simulation of the von
Neumann equation of time-dependent Hamiltonians [65.268245109828]
We develop a general framework to linearize the von-Neumann equation rendering it in a suitable form for quantum simulations.
We show that one of these linearizations of the von-Neumann equation corresponds to the standard case in which the state vector becomes the column stacked elements of the density matrix.
A quantum algorithm to simulate the dynamics of the density matrix is proposed.
arXiv Detail & Related papers (2023-06-14T23:08:51Z) - A hybrid quantum-classical algorithm for multichannel quantum scattering
of atoms and molecules [62.997667081978825]
We propose a hybrid quantum-classical algorithm for solving the Schr"odinger equation for atomic and molecular collisions.
The algorithm is based on the $S$-matrix version of the Kohn variational principle, which computes the fundamental scattering $S$-matrix.
We show how the algorithm could be scaled up to simulate collisions of large polyatomic molecules.
arXiv Detail & Related papers (2023-04-12T18:10:47Z) - Universality of critical dynamics with finite entanglement [68.8204255655161]
We study how low-energy dynamics of quantum systems near criticality are modified by finite entanglement.
Our result establishes the precise role played by entanglement in time-dependent critical phenomena.
arXiv Detail & Related papers (2023-01-23T19:23:54Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
We study the problem of designing worst-case to average-case reductions for quantum algorithms.
We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
arXiv Detail & Related papers (2022-12-06T22:01:49Z) - 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) - Entanglement Forging with generative neural network models [0.0]
We show that a hybrid quantum-classical variational ans"atze can forge entanglement to lower quantum resource overhead.
The method is efficient in terms of the number of measurements required to achieve fixed precision on expected values of observables.
arXiv Detail & Related papers (2022-05-02T14:29:17Z) - Fermionic approach to variational quantum simulation of Kitaev spin
models [50.92854230325576]
Kitaev spin models are well known for being exactly solvable in a certain parameter regime via a mapping to free fermions.
We use classical simulations to explore a novel variational ansatz that takes advantage of this fermionic representation.
We also comment on the implications of our results for simulating non-Abelian anyons on quantum computers.
arXiv Detail & Related papers (2022-04-11T18:00:01Z) - Fixed Depth Hamiltonian Simulation via Cartan Decomposition [59.20417091220753]
We present a constructive algorithm for generating quantum circuits with time-independent depth.
We highlight our algorithm for special classes of models, including Anderson localization in one dimensional transverse field XY model.
In addition to providing exact circuits for a broad set of spin and fermionic models, our algorithm provides broad analytic and numerical insight into optimal Hamiltonian simulations.
arXiv Detail & Related papers (2021-04-01T19:06:00Z)
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.