CS Paper Radar

Conditions for Global Optimality in Quantum Arimoto-Blahut Algorithms

Geng Liu, Masahito Hayashi

cs.IT math.OCquant-ph ·submitted 2026-09-09 05:19 UTC · v1

Abstract

Generalized Arimoto--Blahut (AB) algorithms are widely used in information theory and quantum optimization, but monotonic objective decrease and numerical stabilization do not guarantee global optimality. We establish necessary and sufficient conditions for the global optimality of full-rank AB fixed points for convex differentiable objectives under linear constraints. An AB fixed point is globally optimal if and only if the AB update direction and the objective gradient differ by an element of the constraint normal space at that point. The same compatibility condition characterizes agreement between individual AB and mirror-descent (MD) updates, whereas pathwise equivalence requires it along the entire common trajectory. Thus, an AB algorithm may follow a trajectory different from MD and still reach the global optimum. We also develop a posteriori optimality certificates based on feasible directional derivatives, including finite-difference upper bounds on the objective gap that require only objective evaluations. For channel relative entropy between dephasing and depolarizing channels, we analytically identify the global minimizer as the unique full-rank AB fixed point, although pathwise equivalence fails. Numerical experiments illustrate convergence of AB and MD along different trajectories and validate the certificates. By contrast, an amplitude-damping example shows that a monotone AB iteration can stabilize at a suboptimal fixed point, whose nonoptimality is detected by the finite-difference certificate. These results provide structural and computable criteria for assessing global optimality in quantum AB algorithms.

Closest papers

Nearest neighbours by meaning across the whole index.

Relative-Entropy Geometry and Convergence in Nonconvex Wiretap Optimization

cs.IT quant-ph ·2026-10-13 ·Farzin Salek, Masahito Hayashi
similarity 0.68
Abstract

We develop and analyze an entropic descent method for a nonconvex optimization problem on probability simplices arising in classical and quantum secure communication. The optimization variables describe a randomized encoder, allowing its input distribution and stochastic preprocessing to be optimized jointly. An exact relative-entropy identity yields a channel-independent majorization bound and an explicit mirror-descent iteration with a fixed unit step size. We establish quantitative descent, convergence of objective values, and stationarity of accumulation points on their support faces for arbitrary finite classical channels, without assuming degradedness or less noisiness. For strictly positive transition matrices, a square-root parametrization and a Kurdyka--Łojasiewicz argument establish finite length of the transformed trajectory and convergence of the entire sequence, including limits on the simplex boundary. For less-noisy channels, a restricted convex formulation admits global convergence with an explicit \(O(1/t)\) objective-error bound. We extend the relative-entropy construction to noncommuting quantum outputs and derive monotone alternating updates for covariant encoders, including correlated preprocessing over a fixed block. Numerical experiments compare the method with analytic benchmarks and constrained optimization, reveal multiple attracting values, and demonstrate strict improvements from stochastic preprocessing.

0.08

CV-QAOA: Efficient Low-Depth Quantum Optimization of Continuous Variables

cs.DS quant-ph ·2026-10-05 ·Sriram Bharadwaj, Di Luo, Leo Zhou
theory similarity 0.59
Abstract · 40+41 pages, 9 figures

We study a Continuous-Variable Quantum Approximate Optimization Algorithm (CV-QAOA) for high-dimensional continuous optimization. Our formulation extends an earlier CV-QAOA proposal with a variationally optimized initial state and recovers the convergence guarantees of Quantum Hamiltonian Descent (QHD) in the high-depth limit. We prove rigorous performance guarantees of CV-QAOA on several families of cost functions. First, we show $d$-step CV-QAOA minimizes any $d$-dimensional strictly convex quadratic function with $2d$ quantum queries to the cost function. We then analyze a family of nonconvex "Rotated Double Well" (RDW) functions with $2^d$ local minima introduced by arXiv:2311.00811. While prior work showed QHD reaches its global minimum with $\tilde O(d^3)$ queries, we prove that 1-step CV-QAOA solves RDW with just two quantum queries. Although general-purpose classical solvers need superpolynomial time for RDW and structure-awareness can reduce the cost to polynomial time, we show that the 1-step CV-QAOA protocol can be efficiently dequantized, and that a gradient-aligned line search succeeds with $O(d)$ queries, nearly matching the information-theoretic $Ω(d/\log d)$ query lower bound. To move beyond the dequantizable regime, we introduce a ``Rotated Square Well'' (RSW) problem, whose globally flat landscape suppresses useful local gradient information. For this family, we show that an adiabatic evolution simulated by CV-QAOA can reach the global minimum using $d^{o(1)}$ queries. On the other hand, any classical algorithm that learn the hidden rotation in RSW provably requires $Ω(d^2/\log d)$ queries, a bound we nearly match with an explicit $Θ(d^2\log d)$-query classical algorithm.Numerical simulations on deflected corrugated spring and Easom functions illustrate the promising performance of CV-QAOA on more general problems.

0.11

Complexity Barriers to State Preparation in Quantum Approximate Optimization

cs.CC quant-ph ·2026-09-25 ·Stuart Hadfield
theoryhighly cited similarity 0.59
Abstract

For many important optimization problems we are restricted to approximate solutions in practice due to computational complexity. Distinct from the exact optimization setting, approximate optimization admits performance measures beyond whether the optimum is found, with different tradeoffs and complexity. For MaxCut, a near-unity (ordinary) approximation ratio can coexist with near-zero improvement (gain) over a random cut. For the standard encoding, the unconditional classical MaxCut-Gain hardness gap implies that \emph{any uniformly efficient quantum or hybrid procedure recovering a fixed positive fraction of the optimal classical gain on every input, with at least inverse-polynomial success probability, would place} NP \emph{in} BQP. Such a procedure is therefore believed impossible under standard assumptions. We broadly address where our worst-case barriers do or do not apply across the quantum algorithm landscape. We prove that the barrier survives quantum random access optimization (QRAO) compression and applies between the classical and relaxed optimal values. For every input, a product state attains the classical optimum. Thus the barrier to reaching the classical threshold does not arise from a need for entanglement. For $d\in\{2,3\}$ variables per qubit, the known decoder transfers encoded energy gain to decoded mean gain by the exact factor $1/d^2$. Combining this identity with MaxCut-Gain hardness gives an operational preparation barrier for QRAO. We also construct hard $n$-qubit families with relative quantum relaxation excess $Θ(1/n)$, while the maximally mixed state has energy approximation ratio $1-Θ(1/n)$, zero encoded energy gain, and hence zero decoded mean gain. Our results separate the effects of relaxation tightness and energy approximation from operational accessibility, motivating more comprehensive accounting in benchmarking and performance assessment.

0.39

QC-CCG: Quantum-Classical Algorithm for Two-stage Adaptive Robust Optimization

cs.ET eess.SY ·2026-08-28 ·Duong The Do, Jiaming Cheng, Duong Tung Nguyen
similarity 0.59
Abstract · 12 pages

Quantum optimization provides a promising approach for solving large-scale combinatorial problems through quadratic unconstrained binary optimization (QUBO) formulations. However, integrating QUBO-based solvers into structured optimization frameworks while preserving solution guarantees remains a fundamental challenge. This paper develops a hybrid quantum-classical column-and-constraint generation (QCCG) framework for solving two-stage adaptive robust optimization problems with binary first-stage decisions and linear recourse under polyhedral uncertainty. The proposed approach reformulates the restricted master problem as a QUBO and solves it approximately using a quantum optimizer, while retaining a classical adversarial subproblem to compute worst-case recourse and certify solution quality. We construct a constraint-preserving QUBO encoding for inequality-constrained master problems using slack variables and penalty terms, enabling general mixed-integer structures to be mapped to quantum-compatible representations. To address inexactness arising from discretization, penalty modeling, and quantum optimization, we introduce a bound-adjustment mechanism that yields valid lower and upper bounds and provides a certified stopping criterion. We show that the proposed framework generalizes classical column-and-constraint generation and retains its convergence properties when the master problem is solved exactly. Numerical experiments on two-stage robust location-transportation problems demonstrate that the proposed hybrid approach achieves solution quality comparable to classical methods while reducing the computational burden associated with solving mixed-integer master problems, highlighting the potential of hybrid quantum-classical optimization for scalable decision-making under uncertainty.

0.26

Distributed Hybrid Quantum-Classical Optimization for Robust AoII Minimization in Satellite-Ground Integrated Edge Networks

cs.NI ·2026-10-05 ·Mohammad Arif Hossain, Tanzimul Alam Fahim, Weiqi Liu, Nirwan Ansari
similarity 0.59
Abstract

Edge servers acting on monitored processes need estimates that are correct, not just recent. In satellite-ground integrated networks (SGINs), handover and shadowing interrupt links long enough for the process to change state several times, motivating the age of incorrect information (AoII). We formulate VANGUARD, a robust problem that jointly sets update rates, association, and bandwidth to minimize the worst-case AoII across disruption scenarios, and we solve it with SENTINEL, a distributed hybrid quantum-classical procedure. A renewal-interval decomposition yields a closed-form cost per delivery interval for AoII. The minimax is dualized into classically updated scenario weights, so each domain solves a linear assignment encoded as a compact quadratic unconstrained binary optimization (QUBO) problem with XY-mixer-enforced one-hot constraints; domains are coordinated by the alternating direction method of multipliers (ADMM), and every schedule is certified by its exact worst-case AoII. Under Starlink passes and the 3GPP TR 38.811 channel, the certificate held in 98.7\% of epochs, and the robust one was 2 to 7\% below the nominal one at no cost in realized AoII. The compact encoding uses four to six times fewer qubits than an epigraph encoding; thirteen domains, each 8 to 38 qubits, run on IBM Heron processors and are decoded to the exact optimum.

0.17

Super-Quadratic Quantum Speedups for Combinatorial Optimization via Tilted Walks

cs.DS quant-phmath.OC ·2026-09-30 ·Guneykan Ozgul, Shouvanik Chakrabarti
similarity 0.58
Abstract

We introduce quantum tilted walks, a quantum algorithmic framework for solving exact combinatorial optimization problems. The framework applies an average of powers of a tilted Hamiltonian that biases the discriminant matrix of a base Markov chain (mixer) with the objective function. Our starting point is quantum short-path algorithms, which prepare the ground state of such a Hamiltonian and obtain super-quadratic speedups over exhaustive search for certain combinatorial optimization problems. Recently, Le Gall and Tamaki~(arXiv:2604.12131) developed a classical conditioning-and-search algorithm for weighted MAX-E$k$-LIN2 and weighted MAX-$k$-CSP. Under the same assumptions, their algorithm is only sub-quadratically slower than quantum short-path algorithms. Consequently, existing short-path algorithms do not establish a super-quadratic speedup over this stronger classical baseline. For maximization problems, we give conditions under which tilted walks increase the amplitude on the target state with high objective value when initialized from a starting state with lower objective value. This framework captures conditioning-and-search and yields super-quadratic speedups over it for the same problems. While our framework recovers quantum short-path algorithms as a special case, it neither requires ground-state preparation nor initialization in the ground state of the base mixer. We demonstrate these advantages on a synthetic optimization problem for which tilted walks achieve a super-quadratic speedup whereas the short-path algorithms do not.

0.28

On the Impact of Coordinate Descent for Multi-Angle QAOA in the Independent Set Graph Problem

eess.SP ·2026-10-01 ·Daeyeun Kim, Seungcheol Oh, Joongheon Kim
similarity 0.58
Abstract

Constrained combinatorial optimisation provides a mathematical framework for modelling a wide range of practical decision making problems, including energy network operation, financial portfolio optimisation, logistics, routing, and resource allocation. This paper studies parameter optimisation for the multi angle quantum approximate optimisation algorithm (maQAOA) applied to the maximum independent set problem, a canonical constrained graph based optimisation task. We propose a coordinate wise training framework for maQAOA that updates one variational parameter at a time by solving a sequence of one dimensional optimisation subproblems. For each selected coordinate, the method reconstructs the objective dependence on that parameter and moves directly to the parameter value that minimises the training objective, or equivalently maximises the corresponding expected solution quality. While demonstrated specifically on maQAOA, the underlying theoretical principle, that the expectation value with respect to a given parameter can be analytically expressed as a finite Fourier series, is broadly applicable to general tasks solved via parameterised quantum circuits. Empirical evaluations on connected ErdHos Renyi graph benchmarks demonstrate that this analytic approach significantly reduces the computational training cost required to reach target approximation ratios and yields superior convergence reliability compared to standard gradient based, stochastic, and derivative free baselines.

0.15

Quantum Natural Muon: Spectral-Natural Optimization for Variational Quantum Circuits

eess.SY ·2026-11-06 ·Duong The Do, Duong Tung Nguyen
similarity 0.57
Abstract

Training parameterized quantum circuits requires optimization methods that account for two distinct structures: the information geometry of quantum states and the matrix or tensor structure induced by circuit parameterization. We introduce Quantum Natural Muon (QNM), a spectral natural-gradient framework that applies polar normalization to circuit-semantic parameter blocks after damped quantum Fisher preconditioning. This ordering is essential: quantum Fisher preconditioning and blockwise polar normalization do not commute in general, so QNM is not an order-free composition of quantum natural gradient (QNG) and Muon. We show that Frobenius-matched polar mixing preserves active singular subspaces while raising a spectral floor and improving active conditioning, and that the resulting direction remains a controlled perturbation of QNG. For its distance-aware realization (DA-QNM), we further establish alignment, descent, and nonconvex stationarity guarantees for the normalized update, together with perturbation bounds under gradient and QFIM estimation error. Experiments on variational quantum eigensolving, weighted QAOA-MaxCut, and supervised quantum classification isolate the roles of quantum geometry, circuit-semantic spectral structure, and radius control. The strongest gains arise when the spectral blocks match the circuit structure, supporting the central principle that quantum-state and structured spectral geometries provide complementary information for variational quantum optimization.

0.31