Effectiveness of Binary Autoencoders for QUBO-Based Optimization Problems

• URL: http://arxiv.org/abs/2602.10037v1
• Date: Tue, 10 Feb 2026 17:59:29 GMT
• Title: Effectiveness of Binary Autoencoders for QUBO-Based Optimization Problems
• Abstract summary: In black-box optimization, objective evaluations are often expensive, so high quality solutions must be found under a limited budget.<n>Recent work combines FMQA with a binary autoencoder that learns a compact binary latent code from feasible solutions.<n>We show that the bAE reconstructs feasible tours accurately and, compared with manually designed encodings at similar compression, better aligns tour distances with latent Hamming distances.
• Score: 0.669087470775851
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In black-box combinatorial optimization, objective evaluations are often expensive, so high quality solutions must be found under a limited budget. Factorization machine with quantum annealing (FMQA) builds a quadratic surrogate model from evaluated samples and optimizes it on an Ising machine. However, FMQA requires binary decision variables, and for nonbinary structures such as integer permutations, the choice of binary encoding strongly affects search efficiency. If the encoding fails to reflect the original neighborhood structure, small Hamming moves may not correspond to meaningful modifications in the original solution space, and constrained problems can yield many infeasible candidates that waste evaluations. Recent work combines FMQA with a binary autoencoder (bAE) that learns a compact binary latent code from feasible solutions, yet the mechanism behind its performance gains is unclear. Using a small traveling salesman problem as an interpretable testbed, we show that the bAE reconstructs feasible tours accurately and, compared with manually designed encodings at similar compression, better aligns tour distances with latent Hamming distances, yields smoother neighborhoods under small bit flips, and produces fewer local optima. These geometric properties explain why bAE+FMQA improves the approximation ratio faster while maintaining feasibility throughout optimization, and they provide guidance for designing latent representations for black-box optimization.

Related papers

• Towards Tensor-Network SAT-Solvers for Quantum-Classical Workflows [1.1916225387199697]
  Integrated HPC/QC systems aim to combine classical high-performance computing with quantum processors.<n>An integrated architecture must support aspects such as observability, which cannot be implemented using QPUs alone.
  arXiv  Detail & Related papers  (2026-08-03T10:36:30Z)
• Stage-dependent integer-binary encoding in factorization-machine black-box optimization [0.612477318852572]
  Black-box optimization deals with problems where objective functions lack explicit analytical forms and are expensive to evaluate.<n>We propose a stage-dependent FMQA framework and derive conversion formulas between one-hot and domain-wall QUBO matrices.<n>We evaluate the OhDw variant, which employs one-hot encoding for learning and domain-wall encoding for search.
  arXiv  Detail & Related papers  (2026-06-22T11:36:27Z)
• Comparing Qubit and Qudit Encodings for EV Charging and Trip Assignment Problems [3.56904699288587]
  We study how the choice of encoding affects the resource requirements and optimization behavior of a variational quantum optimization algorithm.<n>We compare a conventional binary (qubit) trip encoding with an integer (qudit) encoding that represents assignments more directly.<n>We find that the qudit encoding of customer trips achieves similar or better optimization performance at much reduced resource requirements and shorter simulation runtime.
  arXiv  Detail & Related papers  (2026-05-11T09:23:29Z)
• BEAM: Bi-level Memory-adaptive Algorithmic Evolution for LLM-Powered Heuristic Design [49.50107918295052]
  Large Language Model-based Hyper Heuristic (LHH) has recently emerged as an efficient way for automatic design.<n>We propose textbfBEAM (Bi-level Memory-adaptive Algorithmic Evolution) to address this problem.<n>We show that BEAM significantly outperforms existing LHHs, notably reducing the optimality gap by 37.84% on aggregate.
  arXiv  Detail & Related papers  (2026-04-14T15:46:47Z)
• Encoding Matters: Benchmarking Binary and D-ary Representations for Quantum Combinatorial Optimization [1.3824488054100907]
  We study Quadratic Unconstrained D-ary Optimization (QUDO) as an alternative formulation in which decision variables are encoded directly in higher dimensional Hilbert spaces.<n>We demonstrate that QUDO naturally captures structural constraints across a range of problem classes, including the Traveling Salesman Problem, graph coloring, job scheduling, and Max-K-Cut, without the need for extensive penalty constructions.<n>Our study show consistently improved approximation ratios and substantially reduced computational overhead at comparable circuit depths, highlighting QUDO as a scalable and expressive representation for quantum optimization.
  arXiv  Detail & Related papers  (2026-02-07T04:37:32Z)
• PT$^2$-LLM: Post-Training Ternarization for Large Language Models [52.4629647715623]
  Large Language Models (LLMs) have shown impressive capabilities across diverse tasks, but their large memory and compute demands hinder deployment.<n>We propose PT$2$-LLM, a post-training ternarization framework tailored for LLMs.<n>At its core is an Asymmetric Ternary Quantizer equipped with a two-stage refinement pipeline.
  arXiv  Detail & Related papers  (2025-09-27T03:01:48Z)
• An Optimization-Free Recursive QAOA for the Binary Paint Shop Problem [0.0]
  The Binary Paint Shop Problem (BPSP) is an optimisation problem found in manufacturing where a sequence of cars are to be painted under certain constraints while minimising the number of colour changes between cars.<n>We show that parameter transfer shows no noticeable reduction in solution quality over optimisation for QAOA and RQAOA.<n>RQAOA only requires measurements of $ZZ$-correlations instead of full statevectors, benefiting from the reverse-causal-cone feature that leads to circuits with significantly lower CNOT counts and depths.
  arXiv  Detail & Related papers  (2025-07-15T01:54:11Z)
• Direct phase encoding in QAOA: Describing combinatorial optimization problems through binary decision variables [0.7015624626359264]
  We show a more qubit-efficient circuit construction for optimization problems by the example of the Travelingperson Sales Problem (TSP)<n>Removing certain redundancies, the number of required qubits can be reduced by a linear factor compared to the aforementioned conventional encoding.<n>Our experiments show that for small instances results are just as accurate using our proposed encoding, whereas the number of required classical iterations increases only slightly.
  arXiv  Detail & Related papers  (2024-12-10T12:12:34Z)
• Quality-Aware Translation Models: Efficient Generation and Quality Estimation in a Single Model [77.19693792957614]
  We propose to make neural machine translation (NMT) models quality-aware by training them to estimate the quality of their own output. We obtain quality gains similar or even superior to quality reranking approaches, but with the efficiency of single pass decoding.
  arXiv  Detail & Related papers  (2023-10-10T15:33:51Z)
• Qubit efficient quantum algorithms for the vehicle routing problem on NISQ processors [48.68474702382697]
  Vehicle routing problem with time windows (VRPTW) is a common optimization problem faced within the logistics industry. In this work, we explore the use of a previously-introduced qubit encoding scheme to reduce the number of binary variables.
  arXiv  Detail & Related papers  (2023-06-14T13:44:35Z)
• Factorizers for Distributed Sparse Block Codes [45.29870215671697]
  We propose a fast and highly accurate method for factorizing distributed block codes (SBCs) Our iterative factorizer introduces a threshold-based nonlinear activation, conditional random sampling, and an $ell_infty$-based similarity metric. We demonstrate the feasibility of our method on four deep CNN architectures over CIFAR-100, ImageNet-1K, and RAVEN datasets.
  arXiv  Detail & Related papers  (2023-03-24T12:31:48Z)
• Efficient Nearest Neighbor Search for Cross-Encoder Models using Matrix Factorization [60.91600465922932]
  We present an approach that avoids the use of a dual-encoder for retrieval, relying solely on the cross-encoder. Our approach provides test-time recall-vs-computational cost trade-offs superior to the current widely-used methods.
  arXiv  Detail & Related papers  (2022-10-23T00:32:04Z)
• Tree ensemble kernels for Bayesian optimization with known constraints over mixed-feature spaces [54.58348769621782]
  Tree ensembles can be well-suited for black-box optimization tasks such as algorithm tuning and neural architecture search. Two well-known challenges in using tree ensembles for black-box optimization are (i) effectively quantifying model uncertainty for exploration and (ii) optimizing over the piece-wise constant acquisition function. Our framework performs as well as state-of-the-art methods for unconstrained black-box optimization over continuous/discrete features and outperforms competing methods for problems combining mixed-variable feature spaces and known input constraints.
  arXiv  Detail & Related papers  (2022-07-02T16:59:37Z)
• Accelerating Bayesian Optimization for Biological Sequence Design with Denoising Autoencoders [28.550684606186884]
  We develop a new approach which jointly trains a denoising autoencoder with a discriminative multi-task Gaussian process head. We evaluate LaMBO on a small-molecule based on the ZINC dataset and introduce a new large-molecule task targeting fluorescent proteins.
  arXiv  Detail & Related papers  (2022-03-23T21:58:45Z)
• Discovering Representations for Black-box Optimization [73.59962178534361]
  We show that black-box optimization encodings can be automatically learned, rather than hand designed. We show that learned representations make it possible to solve high-dimensional problems with orders of magnitude fewer evaluations than the standard MAP-Elites.
  arXiv  Detail & Related papers  (2020-03-09T20:06:20Z)

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.