Optimizing Strongly Interacting Fermionic Hamiltonians

• URL: http://arxiv.org/abs/2110.10701v4
• Date: Thu, 17 Aug 2023 19:59:11 GMT
• Title: Optimizing Strongly Interacting Fermionic Hamiltonians
• Authors: Matthew B. Hastings and Ryan O'Donnell
• Abstract summary: Fundamental problem in much of physics and quantum chemistry is to optimize a low-degree in certain anticommuting variables. One prominent exception is when the optimum is described by a so-called "Gaussian state", also called a free fermion state. We give an efficient classical certification algorithm for upper-bounding the largest eigenvalue in the $q=4$ SYK model, and an efficient quantum certification algorithm for lower-bounding this largest eigenvalue.
• Score: 2.1756081703276
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The fundamental problem in much of physics and quantum chemistry is to optimize a low-degree polynomial in certain anticommuting variables. Being a quantum mechanical problem, in many cases we do not know an efficient classical witness to the optimum, or even to an approximation of the optimum. One prominent exception is when the optimum is described by a so-called "Gaussian state", also called a free fermion state. In this work we are interested in the complexity of this optimization problem when no good Gaussian state exists. Our primary testbed is the Sachdev--Ye--Kitaev (SYK) model of random degree-$q$ polynomials, a model of great current interest in condensed matter physics and string theory, and one which has remarkable properties from a computational complexity standpoint. Among other results, we give an efficient classical certification algorithm for upper-bounding the largest eigenvalue in the $q=4$ SYK model, and an efficient quantum certification algorithm for lower-bounding this largest eigenvalue; both algorithms achieve constant-factor approximations with high probability.

Related papers

• Exponentially Better Bounds for Quantum Optimization via Dynamical Simulation [0.5097809301149342]
  We provide several quantum algorithms for continuous optimization that do not require any gradient estimation. We encode the optimization problem into the dynamics of a physical system and coherently simulate the time evolution.
  arXiv  Detail & Related papers  (2025-02-06T18:32:26Z)
• Gaussian boson sampling for binary optimization [0.0]
  We propose to use a parametrized Gaussian Boson Sampler (GBS) with threshold detectors to address binary optimization problems. Numerical experiments on 3-SAT and Graphing problems show significant performance gains over random guessing.
  arXiv  Detail & Related papers  (2024-12-19T12:12:22Z)
• Classical optimization with imaginary time block encoding on quantum computers: The MaxCut problem [2.4968861883180447]
  Finding ground state solutions of diagonal Hamiltonians is relevant for both theoretical as well as practical problems of interest in many domains such as finance, physics and computer science. Here we use imaginary time evolution through a new block encoding scheme to obtain the ground state of such problems and apply our method to MaxCut as an illustration.
  arXiv  Detail & Related papers  (2024-11-16T08:17:36Z)
• Optimizing Unitary Coupled Cluster Wave Functions on Quantum Hardware: Error Bound and Resource-Efficient Optimizer [0.0]
  We study the projective quantum eigensolver (PQE) approach to optimizing unitary coupled cluster wave functions on quantum hardware. The algorithm uses projections of the Schr"odinger equation to efficiently bring the trial state closer to an eigenstate of the Hamiltonian. We present numerical evidence of superiority over both the optimization introduced in arXiv:2102.00345 and VQE optimized using the Broyden Fletcher Goldfarb Shanno (BFGS) method.
  arXiv  Detail & Related papers  (2024-10-19T15:03:59Z)
• Application of Langevin Dynamics to Advance the Quantum Natural Gradient Optimization Algorithm [47.47843839099175]
  A Quantum Natural Gradient (QNG) algorithm for optimization of variational quantum circuits has been proposed recently.<n>Momentum-QNG is more effective to escape local minima and plateaus in the variational parameter space.
  arXiv  Detail & Related papers  (2024-09-03T15:21:16Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• Quantum algorithms for the variational optimization of correlated electronic states with stochastic reconfiguration and the linear method [0.0]
  We present quantum algorithms for the variational optimization of wavefunctions correlated by products of unitary operators. While an implementation on classical computing hardware would require exponentially growing compute cost, the cost (number of circuits and shots) of our quantum algorithms is in system size.
  arXiv  Detail & Related papers  (2024-08-03T17:53:35Z)
• 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)
• Training variational quantum algorithms is NP-hard [0.7614628596146599]
  We show that the corresponding classical optimization problems are NP-hard. Even for classically tractable systems composed of only logarithmically many qubits or free fermions, we show the optimization to be NP-hard.
  arXiv  Detail & Related papers  (2021-01-18T19:00:01Z)
• GEO: Enhancing Combinatorial Optimization with Classical and Quantum Generative Models [62.997667081978825]
  We introduce a new framework that leverages machine learning models known as generative models to solve optimization problems. We focus on a quantum-inspired version of GEO relying on tensor-network Born machines. We show its superior performance when the goal is to find the best minimum given a fixed budget for the number of function calls.
  arXiv  Detail & Related papers  (2021-01-15T18:18:38Z)
• Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
  Motivated by recent increased interest in analysis of optimization algorithms for non- optimization in deep networks and other problems in data, we give an overview of recent results of theoretical optimization algorithms for non- optimization.
  arXiv  Detail & Related papers  (2020-12-11T08:28:51Z)
• Direct Optimal Control Approach to Laser-Driven Quantum Particle Dynamics [77.34726150561087]
  We propose direct optimal control as a robust and flexible alternative to indirect control theory. The method is illustrated for the case of laser-driven wavepacket dynamics in a bistable potential.
  arXiv  Detail & Related papers  (2020-10-08T07:59:29Z)
• Warm-starting quantum optimization [6.832341432995627]
  We discuss how to warm-start quantum optimization with an initial state corresponding to the solution of a relaxation of an optimization problem. This allows the quantum algorithm to inherit the performance guarantees of the classical algorithm. It is straightforward to apply the same ideas to other randomized-rounding schemes and optimization problems.
  arXiv  Detail & Related papers  (2020-09-21T18:00:09Z)
• Cross Entropy Hyperparameter Optimization for Constrained Problem Hamiltonians Applied to QAOA [68.11912614360878]
  Hybrid quantum-classical algorithms such as Quantum Approximate Optimization Algorithm (QAOA) are considered as one of the most encouraging approaches for taking advantage of near-term quantum computers in practical applications. Such algorithms are usually implemented in a variational form, combining a classical optimization method with a quantum machine to find good solutions to an optimization problem. In this study we apply a Cross-Entropy method to shape this landscape, which allows the classical parameter to find better parameters more easily and hence results in an improved performance.
  arXiv  Detail & Related papers  (2020-03-11T13:52:41Z)

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.