Finite Imaginary-Time Evolution for Polynomial Unconstrained Binary Optimization

• URL: http://arxiv.org/abs/2604.27482v1
• Date: Thu, 30 Apr 2026 06:25:35 GMT
• Title: Finite Imaginary-Time Evolution for Polynomial Unconstrained Binary Optimization
• Abstract summary: We develop a finite-beta structure for diagonal Pauli-Z cost Hamiltonians.<n>The structure yields an exact finite-beta identity between the LCU success probability and the ground-subspace fidelity.
• Score: 5.084371079702479
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Imaginary-time evolution is a standard primitive for ground-state preparation but is nonunitary, precluding direct quantum implementation. We develop Finite Imaginary-Time Evolution (FinITE), a finite-beta construction for diagonal Pauli-Z cost Hamiltonians arising from polynomial unconstrained binary optimization (PUBO) instances, including QUBO and HUBO cases. FinITE uses the linear-combination-of-unitaries (LCU) framework to implement a scaled imaginary-time propagator. The commuting Pauli-Z structure makes termwise block-encodings compose without product-formula error, and higher-order Pauli-Z terms are handled directly without quadratization. The structure yields an exact finite-beta identity between the LCU success probability and the ground-subspace fidelity. Combined with a gap-based fidelity lower bound, the identity yields a closed-form sufficient imaginary-time threshold beta-star for a chosen target fidelity. The threshold depends on estimates of the spectral gap and the initial ground-subspace overlap. Because the LCU success event is flagged by a known ancilla outcome, we integrate fixed-point amplitude amplification with an explicit query-complexity bound. Statevector simulations verify the identity on a five-vertex MaxCut (QUBO) and an eight-qubit cubic HUBO instance, and shot-based simulations on the MaxCut instance illustrate the predicted finite-beta threshold and amplification procedure.

Related papers

• Logarithmic-scale variational quantum eigensolver for off-lattice protein structure prediction in continuous torsional angle space [0.0]
  We propose a logarithmic-scale variational quantum eigensolver (VQE) that reduces qubit requirements for N torsional degrees of freedom to O(log2N)<n>This introduces the first all-atom, continuous-space quantum algorithm for protein structure prediction (QPSP)<n>It proves high-resolution prediction is feasible with exponentially fewer qubits.
  arXiv  Detail & Related papers  (2026-09-02T05:05:46Z)
• Entanglement Quantification via Symmetric Extensions: A Resource Theory Hierarchy [3.662037602213926]
  We introduce a hierarchy of entanglement measures Ek based on k-symmetric PPT extensions.<n>Each Ek, defined via a minimal eigenvalue shift, is faithful, convex, and monotone under free operations.<n>The hierarchy strictly refines PPT-robustness at k = 1, detects bound entanglement at k = 2, and converges exactly to the separability measure as k -> infinity.
  arXiv  Detail & Related papers  (2026-07-18T20:39:35Z)
• Optimality-Preserving Decomposition for Scalable QAOA in Natural-Language-Guided Multi-Drone Assignment [1.189955933770711]
  We present an end-to-end framework integrating a fine-tuned Large Language Model front-end with a highly scalable, domain-specific quantum-classical backend.<n>Our framework features a novel constraint-preserving graph partitioner and a compressed separator-based dynamic programming (DP) merge.<n> Empirical results demonstrate that this architecture circumvents classical scaling walls, recovering the global optimum on 100% of idealized cases and 96.3% under real QAOA sampling.
  arXiv  Detail & Related papers  (2026-06-12T08:31:14Z)
• Super-Level-Set Regression: Conditional Quantiles via Volume Minimization [46.298122008420414]
  We introduce super-level-set regression (SLS), a novel mathematical framework that successfully resolves this implicit coupling.<n>By bypassing full distribution estimation and leveraging flexible volume-preserving frontier functions, our approach captures complex, multimodal, and disjoint conditional structures end-to-end.
  arXiv  Detail & Related papers  (2026-05-07T13:14:45Z)
• Fault-tolerant simulation of the electronic structure using Projector Augmented-Waves and Bloch orbitals [43.936586633107396]
  We present the Bloch--UPAW framework that combines Bloch-orbital $k$-space structure with unitary projector-augmented-wave augmentation.<n>We derive a linear-combination-of-unitaries decomposition and a block-encoding circuit suitable for qubitization.<n>Asymptotically, the Toffoli cost scales as $mathcalO(N_k3)$ when refining the $k$-mesh and as $mathcalO(N_a3.5)$ when enlarging the supercell.
  arXiv  Detail & Related papers  (2026-04-13T23:46:58Z)
• Speculative Decoding Speed-of-Light: Optimal Lower Bounds via Branching Random Walks [39.54576236079211]
  Speculative generation has emerged as a promising technique to accelerate inference in large language models.<n>In this work, we establish the first tight'' lower bounds on the runtime of any deterministic speculative generation algorithm.
  arXiv  Detail & Related papers  (2025-12-12T16:54:33Z)
• Average-case quantum complexity from glassiness [45.57609001239456]
  Glassiness -- a phenomenon in physics characterized by a rough free-energy landscape -- implies hardness for stable classical algorithms.<n>We prove that the standard notion of quantum glassiness based on replica symmetry breaking obstructs stable quantum algorithms for Gibbs sampling.
  arXiv  Detail & Related papers  (2025-10-09T17:37:33Z)
• Spectral Small-Incremental-Entangling: Breaking Quasi-Polynomial Complexity Barriers in Long-Range Interacting Systems [2.911917667184046]
  We introduce the concept of Spectral-Entangling strength, which captures the structural entangling power of an operator.<n>We establish a spectral SIE theorem: a universal speed limit for R'enyi entanglement growth at $alpha ge 1/2$.<n>Our results extend the SIE theorem to the spectral domain and establish a unified framework that unveils the detailed and universal structure underlying quantum complexity.
  arXiv  Detail & Related papers  (2025-09-15T14:56:40Z)
• Zassenhaus Expansion in Solving the Schrödinger Equation [0.0]
  A fundamental challenge lies in approximating the unitary evolution operator ( e-imathcalHt ) where ( mathcalH ) is a large, typically non-commuting, Hermitian operator.<n>We present a refinement of the fixed-depth simulation framework introduced by E. K"okc"u et al, incorporating the second-order Zassenhaus expansion.<n>This yields a controlled, non-unitary approximation with error scaling as ( mathcalO(t
  arXiv  Detail & Related papers  (2025-05-14T14:48:47Z)
• On The Sample Complexity Bounds In Bilevel Reinforcement Learning [49.19950489963245]
  Bilevel reinforcement learning (BRL) has emerged as a powerful framework for aligning generative models.<n>We present the first sample of $mathcalO(epsilon)$ in continuous state-action complexity.<n>Our analysis also extends complexity improving upon existing bounds of $mathcalO(epsilon)$.
  arXiv  Detail & Related papers  (2025-03-22T04:22:04Z)
• Conditional Distribution Quantization in Machine Learning [83.54039134248231]
  Conditional expectation mathbbE(Y mid X) often fails to capture the complexity of multimodal conditional distributions mathcalL(Y mid X)<n>We propose using n-point conditional quantizations--functional mappings of X that are learnable via gradient descent--to approximate mathcalL(Y mid X)
  arXiv  Detail & Related papers  (2025-02-11T00:28:24Z)
• Analyzing Prospects for Quantum Advantage in Topological Data Analysis [35.423446067065576]
  We analyze and optimize an improved quantum algorithm for topological data analysis. We show that super-quadratic quantum speedups are only possible when targeting a multiplicative error approximation. We argue that quantum circuits with tens of billions of Toffoli can solve seemingly classically intractable instances.
  arXiv  Detail & Related papers  (2022-09-27T17:56:15Z)

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.