Optimised Trotter Decompositions for Classical and Quantum Computing

• URL: http://arxiv.org/abs/2211.02691v4
• Date: Fri, 16 Jun 2023 10:09:53 GMT
• Title: Optimised Trotter Decompositions for Classical and Quantum Computing
• Authors: Johann Ostmeyer
• Abstract summary: Suzuki-Trotter decompositions of exponential operators like $exp(Ht)$ are required in almost every branch of numerical physics. We show how highly optimised schemes originally derived for exactly two operators $A_1,2$ can be applied to such generic Suzuki-Trotter decompositions.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Suzuki-Trotter decompositions of exponential operators like $\exp(Ht)$ are required in almost every branch of numerical physics. Often the exponent under consideration has to be split into more than two operators $H=\sum_k A_k$, for instance as local gates on quantum computers. We demonstrate how highly optimised schemes originally derived for exactly two operators $A_{1,2}$ can be applied to such generic Suzuki-Trotter decompositions, providing a formal proof of correctness as well as numerical evidence of efficiency. A comprehensive review of existing symmetric decomposition schemes up to order $n\le4$ is presented and complemented by a number of novel schemes, including both real and complex coefficients. We derive the theoretically most efficient unitary and non-unitary 4th order decompositions. The list is augmented by several exceptionally efficient schemes of higher order $n\le8$. Furthermore we show how Taylor expansions can be used on classical devices to reach machine precision at a computational effort at which state of the art Trotterization schemes do not surpass a relative precision of $10^{-4}$. Finally, a short and easily understandable summary explains how to choose the optimal decomposition in any given scenario.

Related papers

• Exploiting Hankel-Toeplitz Structures for Fast Computation of Kernel Precision Matrices [14.25435308779899]
  Hilbert-space Gaussian Process (HGP) approach offers hyper-independent basis function approximation for speeding up GP inference. In this paper, we lower this dominating computational complexity to $mathcalO(NM)$ with no additional approximations. Our contribution provides a pure speed-up of several existing, widely used, GP approximations, without further approximations.
  arXiv  Detail & Related papers  (2024-08-05T09:45:31Z)
• Unitary tetrahedron quantum gates [3.117417023918577]
  Quantum simulations of many-body systems using 2-qubit Yang-Baxter gates offer a benchmark for quantum hardware. This can be extended to the higher dimensional case with $n$-qubit generalisations of Yang-Baxter gates called $n$-simplex operators. Finding them amounts to identifying unitary solutions of the $n$-simplex equations, the building blocks of higher dimensional integrable systems.
  arXiv  Detail & Related papers  (2024-07-15T13:58:33Z)
• Simple Ways to improve Discrete Time Evolution [0.0]
  Suzuki-Trotter decompositions of exponential operators like $exp(Ht)$ are required in almost every branch of numerical physics. We demonstrate how highly optimised schemes originally derived for exactly two operators can be applied to such generic Suzuki-Trotter decompositions.
  arXiv  Detail & Related papers  (2023-09-06T22:38:29Z)
• Efficient application of the factorized form of the unitary coupled-cluster ansatz for the variational quantum eigensolver algorithm by using linear combination of unitaries [0.0]
  The variational quantum eigensolver is one of the most promising algorithms for near-term quantum computers. It has the potential to solve quantum chemistry problems involving strongly correlated electrons.
  arXiv  Detail & Related papers  (2023-02-17T04:03:06Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  Efficient computation of the optimal transport distance between two distributions serves as an algorithm that empowers various applications. This paper develops a scalable first-order optimization-based method that computes optimal transport to within $varepsilon$ additive accuracy.
  arXiv  Detail & Related papers  (2023-01-30T15:46:39Z)
• Explicit Second-Order Min-Max Optimization Methods with Optimal Convergence Guarantee [86.05440220344755]
  We propose and analyze inexact regularized Newton-type methods for finding a global saddle point of emphcon unconstrained min-max optimization problems. We show that the proposed methods generate iterates that remain within a bounded set and that the iterations converge to an $epsilon$-saddle point within $O(epsilon-2/3)$ in terms of a restricted function.
  arXiv  Detail & Related papers  (2022-10-23T21:24:37Z)
• Two-Unitary Decomposition Algorithm and Open Quantum System Simulation [0.17126708168238122]
  We propose a quantum two-unitary decomposition (TUD) algorithm to decompose a $d$-dimensional operator $A$ with non-zero singular values. The two unitaries can be deterministically implemented, thus requiring only a single call to the state preparation oracle for each. Since the TUD method can be used to implement non-unitary operators as only two unitaries, it also has potential applications in linear algebra and quantum machine learning.
  arXiv  Detail & Related papers  (2022-07-20T16:09:28Z)
• Matching Pursuit Based Scheduling for Over-the-Air Federated Learning [67.59503935237676]
  This paper develops a class of low-complexity device scheduling algorithms for over-the-air learning via the method of federated learning. Compared to the state-of-the-art proposed scheme, the proposed scheme poses a drastically lower efficiency system. The efficiency of the proposed scheme is confirmed via experiments on the CIFAR dataset.
  arXiv  Detail & Related papers  (2022-06-14T08:14:14Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  We provide circuit-level implementations and resource estimates for several methods of block-encoding a dense $Ntimes N$ matrix of classical data to precision $epsilon$. We examine resource tradeoffs between the different approaches and explore implementations of two separate models of quantum random access memory (QRAM) Our results go beyond simple query complexity and provide a clear picture into the resource costs when large amounts of classical data are assumed to be accessible to quantum algorithms.
  arXiv  Detail & Related papers  (2022-06-07T18:00:01Z)
• Average-case Speedup for Product Formulas [69.68937033275746]
  Product formulas, or Trotterization, are the oldest and still remain an appealing method to simulate quantum systems. We prove that the Trotter error exhibits a qualitatively better scaling for the vast majority of input states. Our results open doors to the study of quantum algorithms in the average case.
  arXiv  Detail & Related papers  (2021-11-09T18:49:48Z)
• Higher-order Derivatives of Weighted Finite-state Machines [68.43084108204741]
  This work examines the computation of higher-order derivatives with respect to the normalization constant for weighted finite-state machines. We provide a general algorithm for evaluating derivatives of all orders, which has not been previously described in the literature. Our algorithm is significantly faster than prior algorithms.
  arXiv  Detail & Related papers  (2021-06-01T19:51:55Z)

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.