Product-State Approximation Algorithms for the Transverse Field Ising Model

• URL: http://arxiv.org/abs/2601.13106v1
• Date: Mon, 19 Jan 2026 14:43:42 GMT
• Title: Product-State Approximation Algorithms for the Transverse Field Ising Model
• Abstract summary: We study classical-time approximation algorithms for the transverse-field Ising model (TFIM) Hamiltonian.<n>Our main results are a series of approximation algorithms with respect to the true quantum optimum.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study classical polynomial-time approximation algorithms for the transverse-field Ising model (TFIM) Hamiltonian, allowing a mixture of ferromagnetic and anti-ferromagnetic interactions between pairs of qbits, alongside transverse field terms with arbitrary non-negative weights. Our main results are a series of approximation algorithms (all approximation ratios with respect to the true quantum optimum): (i) a simple maximum of two product state rounding algorithm achieving an approximation ratio $γ\approx 0.71$ , (ii) a strengthened rounding, inspired by the anticommutation property of the two $X_i, Z_iZ_j$ observables achieving ratio $γ\approx 0.7860$, and (iii) a further improvement by interpolation achieving ratio $γ\approx 0.8156$. We also give an explicit (purely ferromagnetic) TFIM instance on three qbits for which every product state achieves at most $169/180\approx 0.9389$ of the true optimum, yielding an upper bound for all algorithms producing product state approximations, even in the purely ferromagnetic case.

Related papers

• Approximating Gaussian Whittle-Matern Fields over Well-Centered Triangulations of Riemannian Manifolds [0.0]
  Markovian Whittle-Matérn fields have been convergently approximated by discrete Gauss Markov Random Fields (GMRFs)<n>We present a different, yet closely related, convergent GMRF approximation to these Matérn fields.<n>We show that, on discretizations that are well-connected in a precise sense, the precision matrices are spectral functions of a graph-laplacian.
  arXiv  Detail & Related papers  (2026-06-11T18:58:55Z)
• On Gaussian approximation for entropy-regularized Q-learning with function approximation [30.147231451149064]
  We derive rates of convergence in the high-dimensional central theorem for Polyak-uppert iterates generated by entropy-regularized asynchronous Q-learning.<n>We establish a Gaussian approximation bound in the convex distance with rate of order $n-1/4$, up to polyarithmic factors in $n$, where $n$ is the number of samples used by the algorithm.
  arXiv  Detail & Related papers  (2026-05-17T22:23:25Z)
• Optimal Approximation of Single Qubit Rotations within a Quantum Circuit [0.12599533416395764]
  Fault-tolerant quantum computing typically requires the transpilation of arbitrary quantum circuits into a finite, universal gate set, such as Clifford+T.<n>As a baseline, Diagonal approximation can be used for single-qubit Pauli rotations.<n>In this work, we present a linear-time algorithm that guarantees an optimal solution to this problem.
  arXiv  Detail & Related papers  (2026-05-10T17:38:53Z)
• Almost Asymptotically Optimal Active Clustering Through Pairwise Observations [59.20614082241528]
  We propose a new analysis framework for clustering $M$ items into an unknown number of $K$ distinct groups using noisy and actively collected responses.<n>We establish a fundamental lower bound on the expected number of queries needed to achieve a desired confidence in the accuracy of the clustering.<n>We develop a computationally feasible variant of the Generalized Likelihood Ratio statistic and show that its performance gap to the lower bound can be accurately empirically estimated.
  arXiv  Detail & Related papers  (2026-02-05T14:16:47Z)
• A Refined Algorithm For the EPR model [0.0]
  Two groups independently develop specific algorithms for the highest-energy state with approximation ratio $frac1+sqrt54approx.809$.<n>Here we try to refine one of the two algorithms by devising homogeneous/quasi-homogeneous fractional matchings.<n>For irregular graphs, we show such a refinement could still guarantee nice performance if the fractional matchings are chosen properly.
  arXiv  Detail & Related papers  (2025-06-10T08:12:14Z)
• Generalized Gradient Norm Clipping & Non-Euclidean $(L_0,L_1)$-Smoothness [51.302674884611335]
  This work introduces a hybrid non-Euclidean optimization method which generalizes norm clipping by combining steepest descent and conditional gradient approaches.<n>We discuss how to instantiate the algorithms for deep learning and demonstrate their properties on image classification and language modeling.
  arXiv  Detail & Related papers  (2025-06-02T17:34:29Z)
• Improved Algorithms for Quantum MaxCut via Partially Entangled Matchings [0.18641315013048299]
  A novel ingredient in both of these algorithms is to partially entangle pairs of qubits associated to edges in a matching.<n>This allows us to interpolate between product states and matching-based states with a tunable parameter.
  arXiv  Detail & Related papers  (2025-04-21T17:59:02Z)
• Beyond likelihood ratio bias: Nested multi-time-scale stochastic approximation for likelihood-free parameter estimation [49.78792404811239]
  We study inference in simulation-based models where the analytical form of the likelihood is unknown.<n>We use a ratio-free nested multi-time-scale approximation (SA) method that simultaneously tracks the score and drives the parameter update.<n>We show that our algorithm can eliminate the original bias $Obig(sqrtfrac1Nbig)$ and accelerate the convergence rate from $Obig(beta_k+sqrtfracalpha_kNbig)$.
  arXiv  Detail & Related papers  (2024-11-20T02:46:15Z)
• Relative-Translation Invariant Wasserstein Distance [82.6068808353647]
  We introduce a new family of distances, relative-translation invariant Wasserstein distances ($RW_p$) We show that $RW_p distances are also real distance metrics defined on the quotient set $mathcalP_p(mathbbRn)/sim$ invariant to distribution translations.
  arXiv  Detail & Related papers  (2024-09-04T03:41:44Z)
• 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)
• Variational Nearest Neighbor Gaussian Process [14.081462755946458]
  Variational approximations to Gaussian processes (GPs) typically use a small set of inducing points to form a low-rank approximation to the covariance matrix. We propose variational nearest neighbor Gaussian process (VNNGP), which introduces a prior that only retains correlations within $K$ nearest-neighboring observations. Using the variational framework, VNNGP's objective can be factorized over both observations and inducing points, enabling optimization with a time complexity of $O(K3)$.
  arXiv  Detail & Related papers  (2022-02-03T17:01:03Z)
• A Law of Iterated Logarithm for Multi-Agent Reinforcement Learning [3.655021726150368]
  In Multi-Agent Reinforcement Learning (MARL), multiple agents interact with a common environment, as also with each other, for solving a shared problem in sequential decision-making. We derive a novel law of iterated for a family of distributed nonlinear approximation schemes that is useful in MARL.
  arXiv  Detail & Related papers  (2021-10-27T08:01:17Z)
• Laplace Matching for fast Approximate Inference in Generalized Linear Models [27.70274403550477]
  We propose an approximate inference framework primarily designed to be computationally cheap while still achieving high approximation quality. The concept, which we call emphLaplace Matching, involves closed-form, approximate, bi-directional transformations between the parameter spaces of exponential families. This effectively turns inference in GLMs into conjugate inference (with small approximation errors)
  arXiv  Detail & Related papers  (2021-05-07T08:25:17Z)
• The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication [61.60069865891783]
  We resolve the min-max complexity of distributed convex optimization (up to a log factor) in the intermittent communication setting. We present a novel lower bound with a matching upper bound that establishes an optimal algorithm.
  arXiv  Detail & Related papers  (2021-02-02T16:18:29Z)

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.