Some improvements to product formula circuits for Hamiltonian simulation
- URL: http://arxiv.org/abs/2310.12256v1
- Date: Wed, 18 Oct 2023 18:43:52 GMT
- Title: Some improvements to product formula circuits for Hamiltonian simulation
- Authors: Andre Kornell and Peter Selinger
- Abstract summary: We present improvements to the standard implementation of the ground state energy estimation algorithm.
These include smaller circuit templates for each Hamiltonian term, parallelization of commuting controlled rotations, and more efficient scheduling.
- Score: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We provide three improvements to the standard implementation of the ground
state energy estimation algorithm via Trotter-Suzuki decomposition. These
consist of smaller circuit templates for each Hamiltonian term, parallelization
of commuting controlled rotations, and more efficient scheduling. These
improvements may be regarded separately, and we anticipate that they may be
combined with other improvements to the standard implementation.
Note that we are not proposing a new algorithm for ground state energy
estimation, nor are we claiming that the Trotter-Suzuki product formula family
of algorithms is the optimal choice for this problem. Rather, we are
demonstrating the use of circuit optimization techniques to give a very
efficient implementation of this particular algorithm.
Related papers
- Self-Supervised Coarsening of Unstructured Grid with Automatic Differentiation [55.88862563823878]
In this work, we present an original algorithm to coarsen an unstructured grid based on the concepts of differentiable physics.<n>We demonstrate performance of the algorithm on two PDEs: a linear equation which governs slightly compressible fluid flow in porous media and the wave equation.<n>Our results show that in the considered scenarios, we reduced the number of grid points up to 10 times while preserving the modeled variable dynamics in the points of interest.
arXiv Detail & Related papers (2025-07-24T11:02:13Z) - Fast Expectation Value Calculation Speedup of Quantum Approximate Optimization Algorithm: HoLCUs QAOA [55.2480439325792]
We present a new method for calculating expectation values of operators that can be expressed as a linear combination of unitary (LCU) operators.<n>This method is general for any quantum algorithm and is of particular interest in the acceleration of variational quantum algorithms.
arXiv Detail & Related papers (2025-03-03T17:15:23Z) - Optimization Algorithm Design via Electric Circuits [13.101300549333297]
We present a novel methodology for convex optimization algorithm design using ideas from electric RLC circuits.
The first stage of the methodology is to design an appropriate electric circuit whose continuous-time dynamics converge to the solution of the optimization problem at hand.
The second stage is an automated, computer-assisted discretization of the continuous-time dynamics, yielding a provably convergent discrete-time algorithm.
arXiv Detail & Related papers (2024-11-04T20:10:59Z) - Strategies for optimizing double-bracket quantum algorithms [0.050257374758179374]
We present strategies to optimize the choice of the double-bracket evolutions.
We also present a selection of diagonal evolution parametrizations that can be directly compiled into CNOTs and single-qubit rotation gates.
arXiv Detail & Related papers (2024-08-14T10:07:54Z) - Approximating exponentials of commutators by optimized product formulas [0.0]
Trotter product formulas constitute a cornerstone quantum Hamiltonian simulation technique.
We construct optimized product formulas of orders 3 to 6 approximating the exponential of a commutator of two arbitrary operators.
arXiv Detail & Related papers (2024-07-15T08:41:00Z) - Multi-product Hamiltonian simulation with explicit commutator scaling [2.5677613431426978]
The well-conditioned multi-product formula (MPF) is a simple high-order time-independent Hamiltonian simulation algorithm.
We conduct a rigorous analysis of the MPF, demonstrating explicit commutator scaling and near-optimal time and precision dependence.
Compared to post-Trotter methods, the MPF based on a second-order product formula can achieve a better scaling in system size, with only poly-logarithmic overhead in evolution time and precision.
arXiv Detail & Related papers (2024-03-13T19:23:59Z) - Tractable Bounding of Counterfactual Queries by Knowledge Compilation [51.47174989680976]
We discuss the problem of bounding partially identifiable queries, such as counterfactuals, in Pearlian structural causal models.
A recently proposed iterated EM scheme yields an inner approximation of those bounds by sampling the initialisation parameters.
We show how a single symbolic knowledge compilation allows us to obtain the circuit structure with symbolic parameters to be replaced by their actual values.
arXiv Detail & Related papers (2023-10-05T07:10:40Z) - Predicting Ordinary Differential Equations with Transformers [65.07437364102931]
We develop a transformer-based sequence-to-sequence model that recovers scalar ordinary differential equations (ODEs) in symbolic form from irregularly sampled and noisy observations of a single solution trajectory.
Our method is efficiently scalable: after one-time pretraining on a large set of ODEs, we can infer the governing law of a new observed solution in a few forward passes of the model.
arXiv Detail & Related papers (2023-07-24T08:46:12Z) - Accelerating Cutting-Plane Algorithms via Reinforcement Learning
Surrogates [49.84541884653309]
A current standard approach to solving convex discrete optimization problems is the use of cutting-plane algorithms.
Despite the existence of a number of general-purpose cut-generating algorithms, large-scale discrete optimization problems continue to suffer from intractability.
We propose a method for accelerating cutting-plane algorithms via reinforcement learning.
arXiv Detail & Related papers (2023-07-17T20:11:56Z) - Trotter error bounds and dynamic multi-product formulas for Hamiltonian
simulation [3.2995359570845912]
We extend the theory of Trotter error with commutator scaling to multi-product formulas.
We introduce dynamic multi-product formulas with time-dependent coefficients chosen to minimize a certain efficiently computable proxy for the Trotter error.
We use a minimax estimation method to make dynamic multi-product formulas robust to uncertainty from algorithmic errors, sampling and hardware noise.
arXiv Detail & Related papers (2023-06-21T21:07:06Z) - Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
We exploit between first-order algorithms for constrained optimization and non-smooth systems to design a new class of accelerated first-order algorithms.
An important property of these algorithms is that constraints are expressed in terms of velocities instead of sparse variables.
arXiv Detail & Related papers (2023-02-01T08:50:48Z) - Iterative Linear Quadratic Optimization for Nonlinear Control:
Differentiable Programming Algorithmic Templates [9.711326718689495]
We present the implementation of nonlinear control algorithms based on linear and quadratic approximations of the objective from a functional viewpoint.
We derive the computational complexities of all algorithms in a differentiable programming framework and present sufficient optimality conditions.
The algorithms are coded in a differentiable programming language in a publicly available package.
arXiv Detail & Related papers (2022-07-13T17:10:47Z) - Improved performance in quantum transport calculations: A
divide-and-conquer method based on S-matrices [0.0]
We propose a divide-and-conquer algorithm to find the Scattering matrix of general tight-binding structures.
The Scattering matrix allows a direct calculation of transport properties in mesoscopic systems by using the Landauer formula.
arXiv Detail & Related papers (2022-04-27T04:14:00Z) - Twisted hybrid algorithms for combinatorial optimization [68.8204255655161]
Proposed hybrid algorithms encode a cost function into a problem Hamiltonian and optimize its energy by varying over a set of states with low circuit complexity.
We show that for levels $p=2,ldots, 6$, the level $p$ can be reduced by one while roughly maintaining the expected approximation ratio.
arXiv Detail & Related papers (2022-03-01T19:47:16Z) - Efficient Product Formulas for Commutators and Applications to Quantum
Simulation [4.523323031658363]
We construct product formulas for exponentials of commutators.
We show how to use the product formulas in a digital protocol for counterdiabatic driving.
arXiv Detail & Related papers (2021-11-23T22:27:20Z) - Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
Bilevel optimization has been widely applied in many important machine learning applications.
We propose two new algorithms for bilevel optimization.
We show that both algorithms achieve the complexity of $mathcalO(epsilon-1.5)$, which outperforms all existing algorithms by the order of magnitude.
arXiv Detail & Related papers (2021-06-08T21:05:30Z) - A Reinforcement Learning Environment for Polyhedral Optimizations [68.8204255655161]
We propose a shape-agnostic formulation for the space of legal transformations in the polyhedral model as a Markov Decision Process (MDP)
Instead of using transformations, the formulation is based on an abstract space of possible schedules.
Our generic MDP formulation enables using reinforcement learning to learn optimization policies over a wide range of loops.
arXiv Detail & Related papers (2021-04-28T12:41:52Z) - Adaptive pruning-based optimization of parameterized quantum circuits [62.997667081978825]
Variisy hybrid quantum-classical algorithms are powerful tools to maximize the use of Noisy Intermediate Scale Quantum devices.
We propose a strategy for such ansatze used in variational quantum algorithms, which we call "Efficient Circuit Training" (PECT)
Instead of optimizing all of the ansatz parameters at once, PECT launches a sequence of variational algorithms.
arXiv Detail & Related papers (2020-10-01T18:14:11Z) - Adaptivity of Stochastic Gradient Methods for Nonconvex Optimization [71.03797261151605]
Adaptivity is an important yet under-studied property in modern optimization theory.
Our algorithm is proved to achieve the best-available convergence for non-PL objectives simultaneously while outperforming existing algorithms for PL objectives.
arXiv Detail & Related papers (2020-02-13T05:42:27Z) - Accelerating Feedforward Computation via Parallel Nonlinear Equation
Solving [106.63673243937492]
Feedforward computation, such as evaluating a neural network or sampling from an autoregressive model, is ubiquitous in machine learning.
We frame the task of feedforward computation as solving a system of nonlinear equations. We then propose to find the solution using a Jacobi or Gauss-Seidel fixed-point method, as well as hybrid methods of both.
Our method is guaranteed to give exactly the same values as the original feedforward computation with a reduced (or equal) number of parallelizable iterations, and hence reduced time given sufficient parallel computing power.
arXiv Detail & Related papers (2020-02-10T10:11:31Z)
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.