Qubit-efficient quantum local search for combinatorial optimization

M. Podobrii; M. R. Perelshtein; M. Veshchezerova; V. Kuzmin; V. Voloshinov

REVIEW 4 major objections 4 minor 41 references

Qubit-efficient quantum local search for combinatorial optimization

T0 review · 4 major / 4 minor · reviewed 2026-08-09 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read A variational quantum circuit runs r-local search over a neighborhood of size l with only logarithmically many qubits.

desk verdict The group-flip encoding is a real and honestly presented idea, but finite-shot sampling structurally caps the effective neighborhood at the number of shots, so the classically-intractable-l claim does not survive contact with near-term hardware. read the letter →

arxiv 2502.02245 v1 pith:XACZLMHI submitted 2025-02-04 quant-ph

M. Podobrii , V. Kuzmin , V. Voloshinov , M. Veshchezerova , M. R. Perelshtein This is my paper · ORCID

classification quant-ph

keywords variationalquantumalgorithmqubit-efficientencodingr-localsearchcombinatorialoptimizationMaxCutgraphcoloringQUBOIsingmodel

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper claims that a variational quantum algorithm can perform r-local search, the routine at the heart of most optimization metaheuristics, over a neighborhood of size l using only $\lceil \log_2 l \rceil$ qubits. The key move is to encode not the candidate solution itself but the probabilities of flipping groups of variables, and to minimize an auxiliary multilinear function whose local minima coincide with those of r-local search. If the claim holds, near-term devices with modest qubit counts could search neighborhoods that are classically intractable to enumerate, and increasing the neighborhood size would improve solution quality without a blow-up in the required number of measurements. The authors demonstrate this numerically on MaxCut instances up to 512 nodes and on a 191-vertex graph coloring problem, the largest graph coloring instance solved by a quantum method to date, plus a test on a real noisy processor.

What carries the argument

The load-bearing object is the auxiliary multilinear function $E(\vec{q})$ of Eq. (9), built by writing each original spin as a product of flip variables over a chosen collection of groups, then relaxing the discrete flip variables to continuous values in $[-1,1]$. Its local minima are exactly the solutions that beat every neighbor reachable by flipping one encoded group, so minimizing it is r-local search over that neighborhood. The quantum part encodes group indices in $\lceil \log_2 l \rceil$ qubits, converts measured outcome probabilities $P_\mu$ into auxiliary variables $q_\mu$ through the monotone transformation $q_\mu = \frac{2\tanh(\alpha(1-MP_\mu))+1}{\tanh \alpha + 1} - 1$ (Eq. (11)), and optimizes the composite function with a hardware-efficient circuit using the parameter-shift rule for gradients. Sparse problems restrict groups to connected subgraphs, which provably removes redundant neighbors, and the finite-shot estimate of the auxiliary function runs in time polynomial in the problem size, the shot count, the layer count, and $\log l$, not in $l$.

What would settle it

On a fixed 3-regular MaxCut-512 graph, run the algorithm with r=1 (l=512, 9 qubits) and r=4 (l=6367, 13 qubits) from the same random initial solutions at the same circuit depth; if the r=4 approximation-ratio distribution does not stochastically dominate the r=1 one and reach the classical r=4 local-search baseline, the central claim that larger neighborhoods improve solutions would be refuted. A second check targets the shot-count claim: for fixed M=200 on a MaxCut-256 graph, the mean-squared-error curve versus shot count should be independent of r; a measured rightward shift as r grows from 1 to 7 would falsify it.

Watch

Extended reading notes

Core claim

The paper's central claim is that r-local search can be quantized by replacing discrete flip variables with continuous probabilities attached to flips of chosen groups of spins, then minimizing the resulting auxiliary function with a parametrized quantum circuit. For a chosen neighborhood of size l, the algorithm needs only $\lceil \log_2 l \rceil$ qubits: each computational basis outcome is decoded into a group of spins to flip, and the measured probabilities are mapped to auxiliary variables in $[-1,1]$ through a monotone transformation. The authors establish that local minima of the auxiliary function correspond exactly to solutions better than all neighbors in the encoded neighborhood, so optimizing it is equivalent to r-local search; the finite-shot estimate of the function has mean-squared error whose onset depends on the hyperparameter M, not on the neighborhood size l. Numerically, increasing the neighborhood size improves approximation ratios on MaxCut-512, the myciel7 graph coloring problem is solved in 19 of 100 runs with 13 qubits, and the r=n limit matches complete-encoding VQE while r=1 outperforms minimal encoding at shallow depth.

Load-bearing premise

Everything rests on the assumption that optimizing the circuit's rotation angles, rather than the flip probabilities directly, drives the measured distribution to a minimum of the auxiliary function that is as good as r-local search; the paper states in Section 3 that the local-minima proof no longer applies once the circuit parameters are optimized, and the numerical evidence covers only moderate neighborhood sizes.

Editorial extensions

If this is right

Any problem whose neighborhood can be decoded from a bitstring becomes addressable with $\lceil \log_2 l \rceil$ qubits, so neighborhood sizes that are classically intractable to enumerate are in principle reachable on near-term hardware.
Increasing the neighborhood size improves solution quality once the circuit is deep enough; the MaxCut-512 experiments show the average approximation ratio rising from r=1 to r=4 at fixed depth.
The shot count needed for fixed-accuracy estimation of the auxiliary function is governed by the hyperparameter M, not by l, so a user can trade measurements against the effective number of local-search steps per round.
At the r=n limit the method matches complete-encoding VQE, while at r=1 it matches bilinear relaxation and improves on minimal encoding for shallow circuits, so the encoding continuously interpolates between the two established extremes.
Sampling several most-probable solutions from the final flip-probability distribution mitigates hardware noise, because a distorted distribution still ranks many good candidates near the top.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

An implication the authors leave implicit is that the group-selection step is the real problem-design lever: for constrained problems, choosing flip groups that preserve feasibility, as the color-switch groups do for graph coloring, is what converts an infeasible 1-local search landscape into a useful one, and the same recipe should transfer to other constraint-heavy QUBO formulations.
Because the algorithm outputs a ranked list of most-probable flip sets rather than a single solution, it could serve as the neighborhood generator inside classical metaheuristics such as tabu search or simulated annealing; the paper only notes this direction in passing.
A testable prediction implicit in Fig. 7 is that the number of variational parameters needed to match classical r-local search grows sublinearly in l; checking whether this holds for larger r or on fully connected graphs would separate a property of the encoding from a property of the sparse MaxCut instances used.
The M-hyperparameter bound on negative $q_\mu$ components means each round can realize at most about M improving flips from the initial solution, which is why restarts are needed; this suggests a natural hybrid variant in which the quantum circuit proposes candidates and a classical routine verifies them, a combination the authors hint at but do not develop.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

You should know two things about this paper. First, the core construction is legitimate: an auxiliary function over group-flip variables whose local minima coincide with r-local search, plus a log-qubit encoding of the group index and a tanh map from measurement probabilities to flip probabilities. The Proposition 2 argument is correctly applied, and the paper is unusually candid; it explicitly states in Section 3 that the local-minima equivalence no longer holds once you optimize circuit parameters theta instead of q directly. Second, the headline claim about classically intractable neighborhood sizes is not supported by the paper's own finite-shot analysis. The stress-test note is right: q_mu(0)=1, so any group that is never sampled is never flipped. With N shots you see at most N distinct outcomes, so at most N groups ever get q_mu<1, and the optimizer receives no gradient signal for unsampled groups. The effective neighborhood is bounded by N, independent of the encoded l. Section 4.2's observation that the estimate has 'no more than N nonzero components' cuts both ways: it is a search-space bound, not just a sparse-format convenience. Exploring l much larger than N would require shot counts comparable to l, which is exactly the classical cost the abstract promises to escape.

Credit where it is due: the numerical work is real, if heuristic. MaxCut-512 with l up to 6367 groups shows the encoding working for moderate l, and performance tracks or slightly beats classical local search in the same neighborhood; though that is partly a consistency check by construction, since the auxiliary minima were designed to match. The myciel7 coloring result (19/100 runs) is a concrete data point, but with no classical baseline, per-instance hyperparameters, and no code or data, I would not lean on the 'largest instance solved by a quantum method' claim. The shot-accuracy analysis (MSE scaling as 1/N, independent of l) is genuinely useful and under-appreciated.

Who should read it: anyone working on qubit-efficient variational optimization or NISQ heuristics. It deserves a serious referee; the encoding is novel relative to the minimal-encoding literature, and the authors are honest about the trainability gap. But the scalability claim needs re-framing around the shot budget, and the authors should be pressed to release code and data. I would referee it, and I would condition acceptance on addressing the N-versus-l bound.

Referee Report

4 major / 4 minor

Summary. The paper introduces a variational quantum algorithm for local search on Ising/QUBO optimization problems. The authors define an auxiliary continuous function over group-flip variables whose local minima coincide with those of r-local search, map measurement-outcome probabilities to those auxiliary variables through a tanh transformation, and optimize a hardware-efficient ansatz. The claimed contribution is a qubit-efficient scheme using only ceil(log2 l) qubits that can in principle handle classically intractable neighborhood sizes on near-term devices. Numerical demonstrations include MaxCut-512, a graph coloring instance (myciel7), and a small QPU experiment.

Significance. If the central near-term scalability claim were valid, the paper would represent a significant step toward using few qubits for large combinatorial optimization problems. The formal reduction in Sec. 2, connecting the auxiliary function's local minima to r-local search, is correct and clearly presented; the variable number of qubits and problem-specific neighborhood selection for graph coloring are also useful ideas. The resource analysis in Sec. 4.2 and the sparse-evaluation observation in Sec. 4.3 are reasonable for fixed-point estimation. However, the central claim about classically intractable neighborhoods is not supported once finite-shot sampling and the actual optimization over circuit parameters are taken into account. The paper's own acknowledgement in Sec. 3 that the local-minima analysis no longer applies, together with the finite-shot bottleneck discussed below, means that the advertised advantage rests on unproven and structurally questionable assumptions.

major comments (4)

[Sec. 3.4, Eq. (11)] The finite-shot sampling step severely limits the effective neighborhood size to at most N groups. With N measurement shots, at most N outcomes have non-zero estimated probability; every other outcome is assigned q_mu = 1 via Eq. (11), meaning that the corresponding group is never flipped and contributes nothing to the objective or to the gradient in Eq. (13). During finite-shot optimization, the optimizer cannot redirect probability toward a good group unless that group has been sampled. The claim that the algorithm 'can potentially work with classically intractable neighborhood sizes' (Abstract, Sec. 4.3) is therefore unsupported for near-term devices. The only finite-shot experiment (Sec. 6.4) uses l = 128 with N = 1000 shots, while the large-l results in Secs. 6.2 and 6.3 use exact state-vector simulation where all 2^Nq outcomes are visible. A concrete test would be to run the optimization with N << l and measure success probability as a function of N; without such evidence, the central scalability claim is not established.
[Sec. 3, first paragraph] The authors explicitly state that 'the previous analysis of the local minima is no longer applicable' once the circuit parameters, rather than the auxiliary variables q, are optimized. This removes the theoretical guarantee that the algorithm implements r-local search. The numerical evidence in Sec. 6.2 is heuristic, uses per-instance hyperparameters, and shows only average approximation ratios relative to classical local search; it does not establish that optimizing theta over the hardware-efficient ansatz subspace yields r-local-search-quality solutions in general. The central theoretical contribution of the paper is therefore limited to direct optimization of the auxiliary function, not to the variational quantum algorithm as actually executed.
[Sec. 4.2, Fig. 4] The MSE analysis addresses fixed-point estimation of the auxiliary function, not the difficulty of optimizing it. The observation that the MSE starts decreasing only when N is comparable to M is consistent with the finite-shot bottleneck, and the left panel of Fig. 4 shows that MSE decreases for larger l only because the landscape becomes flatter. Flatness is itself a trainability obstacle, as the authors acknowledge in Sec. 2.2 and Sec. 4.1. Therefore the conclusion that 'the number of shots required to estimate it with a fixed accuracy doesn't grow with l' does not support the stronger claim that optimization can handle classically intractable l.
[Sec. 6.3] The graph coloring result is based on 19 successful runs out of 100 on a single instance (myciel7), with problem-specific group selection and hyperparameters. The claim of solving 'the largest graph coloring instance tackled by a quantum algorithm' is weakened by the low success rate and by the absence of a direct comparison to a classical local search baseline within the same neighborhood. Without such a baseline, it is difficult to attribute the obtained solutions to the quantum algorithm rather than to the restart strategy or the problem-specific neighborhood construction.

minor comments (4)

[Sec. 3.2, Eq. (11)] The typesetting of Eq. (11) is ambiguous: the placement of the quotient and the '+1 - 1' term is unclear. Please rewrite the formula with explicit parentheses so that the intended functional form is unambiguous.
[Sec. 6.2] The statement that the quantum algorithm achieves solutions 'slightly superior' to classical local search attributes the improvement to multiple optimization rounds, but the classical baseline is not given the same restart (R = 10) treatment. A fairer comparison would allow the classical local search to restart from the same initial solutions.
[Sec. 5.2] The classical local search uses a first-improvement strategy with a fixed lexicographic ordering of groups. The choice of ordering can significantly affect local search outcomes; a brief discussion or sensitivity check would be helpful.
[Sec. 4.2] The discussion of the flat landscape for large l in the left panel of Fig. 4 would benefit from an explicit caveat that the reduced MSE is a consequence of reduced variance in a flat landscape, not an indication that optimization becomes easier.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the auxiliary-function construction is an explicit reduction, benchmarks are external, and the finite-shot concern is a scalability issue, not a circular one.

full rationale

The derivation is self-contained. Equation (9) is obtained by substituting the group-flip decoding Eq. (6) into the Ising energy and relaxing the discrete z_k to continuous q_k; the claim that its local minima coincide with r-local-search minima is proved from Proposition 2, a standard property of multilinear functions on a hypercube, with the proof given in the text and the proposition attributed to external Ref. [24]. The numerical comparison with classical local search in Sec. 6.2 is therefore a consistency check of the construction rather than a circular prediction, and the paper explicitly acknowledges in Sec. 3 that once circuit parameters are optimized the formal equivalence no longer applies. The qubit-efficiency and shot-complexity arguments in Secs. 4.2 and 4.3 are resource estimates based on the proposed q(P) map; they may be debatable, since the finite-shot cap at N nonzero components limits the effective neighborhood explored on real hardware, but that is a correctness and scalability concern, not a reduction of a prediction to its inputs. The only self-citation, Ref. [9] by some of the same authors, is used as a benchmark baseline for minimal encoding and is not load-bearing for the central claim. No fitted parameter is renamed as a prediction, and no uniqueness theorem is imported from the authors' prior work.

Assumptions & free parameters 5 free parameters · 5 assumptions · 0 invented entities

The core math is standard multilinear relaxation; the paper-specific load is carried by the probability-to-variable mapping Eq. (11) and by the unproven trainability of the hardware-efficient ansatz. Hyperparameters alpha, M, L, R, S are chosen per instance and affect all reported results.

free parameters (5)

alpha = 2 (MaxCut-256), 7 (MaxCut-512), 4 (graph coloring), 2 (QPU), 2 or 3 (Appendix A)
Controls steepness of Eq. (11); chosen per problem to reduce flat landscape; no selection rule given.
M = 256 (MaxCut-256), 512 (MaxCut-512), 1000 (graph coloring), 128 (QPU), 2 to 2000 in shot-scaling study
Limits number of negative q values to at most M, hence limits the number of flips per round; chosen per problem; shot requirement scales with M.
L (layers) = Up to 20; Fig. 7 fits the minimal L needed to match classical local search
Circuit depth needed for expressivity; no theory for required depth; numbers fitted to empirical matching.
R (restart rounds) = 1 to 10 depending on experiment
Number of local search rounds; chosen heuristically.
S (samples) = 1, 10, 500, or 512 depending on experiment
Number of most probable solutions decoded; chosen per experiment.

assumptions (5)

standard math Proposition 1 and Proposition 2 from Ref. [24]: multilinear functions on a hypercube have local minima only at vertices, and a vertex is a local minimum iff single-variable flips do not decrease the value.
Used in Section 2.1 to equate bilinear relaxation minima with 1-local search minima, and in Section 2.2 to argue Eq. (9) minima match group-flip local search.
domain assumption The original problem can be represented as an Ising model and the solution can be encoded as a product of group flips Eq. (6), with z_k treated as independent Bernoulli variables.
Section 2.2; the auxiliary function averages over an independent flip distribution, so correlations between flips are neglected.
domain assumption A hardware-efficient ansatz of sufficient depth can approximate the relevant region of q-space well enough that optimizing circuit parameters yields decoded solutions comparable to r-local search.
Section 3 admits the earlier local-minima analysis no longer applies; numerical evidence is limited to l up to 6367 groups.
ad hoc to paper The transformation Eq. (11), q_mu = 2 tanh(alpha(1 - M P_mu)) / tanh(alpha) + 1 - 1, with hyperparameters alpha and M, is a suitable bridge between measurement probabilities and auxiliary variables.
Introduced to make the landscape less flat and to limit negative q values; no principled derivation is provided.
domain assumption Finite-shot estimates of P, with at most N nonzero entries, suffice for optimizing E(q(P(theta))); the analysis in Section 4.2 covers fixed-point estimation error, not optimization error.
Section 4.2 shows the MSE of the cost estimate scales as 1/N for N much larger than M, but does not prove trainability of the optimization trajectory.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Qubit-efficient quantum local search for combinatorial optimization." pith.science (2026). https://pith.science/paper/XACZLMHI

@misc{pith2026250202245,
  author       = {Pith},
  title        = {Pith review of: Qubit-efficient quantum local search for combinatorial optimization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/XACZLMHI}},
  note         = {Machine review of arXiv:2502.02245}
}

abstract

An essential component of many sophisticated metaheuristics for solving combinatorial optimization problems is some variation of a local search routine that iteratively searches for a better solution within a chosen set of immediate neighbors. The size $l$ of this set is limited due to the computational costs required to run the method on classical processing units. We present a qubit-efficient variational quantum algorithm that implements a quantum version of local search with only $\lceil \log_2 l \rceil$ qubits and, therefore, can potentially work with classically intractable neighborhood sizes when realized on near-term quantum computers. Increasing the amount of quantum resources employed in the algorithm allows for a larger neighborhood size, improving the quality of obtained solutions. This trade-off is crucial for present and near-term quantum devices characterized by a limited number of logical qubits. Numerically simulating our algorithm, we successfully solved the largest graph coloring instance that was tackled by a quantum method. This achievement highlights the algorithm's potential for solving large-scale combinatorial optimization problems on near-term quantum devices.

Figures

Figures reproduced from arXiv: 2502.02245 by the authors.

**Figure 2.** Plots of the transformation qµ(Pµ) for different values of the hyperparameter α. The property qµ(0) = 1 implies that if the outcome µ was not measured in N rounds, the corresponding variable qµ gets value 1. Therefore, our encoding avoids the issue present in minimal encoding [8, 9], where outcomes that did not occur lead to an undefined bit value. 3.3 Variational circuit We use a common approach to address optimiza… view at source ↗

**Figure 3.** Ansatz with 6 qubits and 2 layers 3.4 Optimization process After substituting Eq. (11) into Eq. (9) and introducing a parameterized quantum circuit, we obtain a composite auxiliary function E = E h ⃗q P⃗ ( ⃗θ) i. Here, we outline how to optimize it and get the solution to the original problem. Initial solution selection: First, we choose an initial solution by fixing Z⃗(0) in Eq. (9). Typically, it may be a state… view at source ↗

Figures from the paper (6 more)

**Figure 4.** Figure 4: Mean squared error of the auxiliary function estimation obtained with a finite number of [PITH_FULL_IMAGE:figures/full_fig_p013_4.png]

**Figure 5.** Figure 5: Approximation ratios of solutions obtained by our algorithm with [PITH_FULL_IMAGE:figures/full_fig_p015_5.png]

**Figure 6.** Figure 6: Left: the average approximation ratio for MaxCut-512 found by the algorithm with different [PITH_FULL_IMAGE:figures/full_fig_p016_6.png]

**Figure 7.** Figure 7: Number of circuit parameters required for reaching the same average approximation ratio as [PITH_FULL_IMAGE:figures/full_fig_p017_7.png]

**Figure 8.** Figure 8: Left: Convergence of parameter optimization with SPSA over iterations using a numerical [PITH_FULL_IMAGE:figures/full_fig_p018_8.png]

**Figure 9.** Figure 9: Left: the average approximation ratio of the top 20% of solutions for Ising-20 found by VQE [PITH_FULL_IMAGE:figures/full_fig_p021_9.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

41 extracted references · 37 canonical work pages

[1]

An efficient closed-form formula for evaluating r-flip moves in quadratic unconstrained binary optimization

Bahram Alidaee, Haibo Wang, and Lutfu S. Sua. “An efficient closed-form formula for evaluating r-flip moves in quadratic unconstrained binary optimization”. Algorithms 16, 557 (2023)

work page 2023
[2]

Optimization by simulated annealing

S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi. “Optimization by simulated annealing”. Science 220, 671–680 (1983)

work page 1983
[3]

Multistart tabu search strategies for the unconstrained binary quadratic optimization problem

Gintaras Palubeckis. “Multistart tabu search strategies for the unconstrained binary quadratic optimization problem”. Annals of Operations Research131, 259–282 (2004)

work page 2004
[4]

Memetic algorithms for the unconstrained binary quadratic programming problem

Peter Merz and Kengo Katayama. “Memetic algorithms for the unconstrained binary quadratic programming problem”. Bio Systems78, 99–118 (2005)

work page 2005
[5]

Metaheuristic algorithms

Yang Wang and Jin-Kao Hao. “Metaheuristic algorithms”. Pages 241–259. Springer International Publishing. Cham (2022)

work page 2022
[6]

Quantum Local Search with the Quantum Alternating Operator Ansatz

Teague Tomesh, Zain H. Saleem, and Martin Suchara. “Quantum Local Search with the Quantum Alternating Operator Ansatz”. Quantum6, 781 (2022)

work page 2022
[7]

Reinforcement learning quantum local search

Chen-Yu Liu and Hsi-Sheng Goan. “Reinforcement learning quantum local search”. In 2023 IEEE International Conference on Quantum Computing and Engineering (QCE). Page 246–247. IEEE (2023)

work page 2023
[8]

Qubit-efficient encoding schemes for binary optimisation problems

Benjamin Tan, Marc-Antoine Lemonde, Supanut Thanasilp, Jirawat Tangpanitanon, 24 and Dimitris G. Angelakis. “Qubit-efficient encoding schemes for binary optimisation problems”. Quantum 5, 454 (2021)

work page 2021

Show all 41 references

[9]

NISQ-compatible approximate quantum algorithm for unconstrained and constrained discrete optimiza- tion

M. R. Perelshtein, A. I. Pakhomchik, Ar. A. Melnikov, M. Podobrii, A. Termanova, I. Kreidich, B. Nuriev, S. Iudin, C. W. Mansell, and V. M. Vinokur. “NISQ-compatible approximate quantum algorithm for unconstrained and constrained discrete optimiza- tion”. Quantum 7, 1186 (2023)

2023
[10]

A variational qubit- efficient maxcut heuristic algorithm

Yovav Tene-Cohen, Tomer Kelman, Ohad Lev, and Adi Makmal. “A variational qubit- efficient maxcut heuristic algorithm” (2023). arXiv:2308.10383

2023 arXiv
[11]

Solving various NP-hard problems using exponentially fewer qubits on a quantum computer

Yagnik Chatterjee, Eric Bourreau, and Marko J. Rančić. “Solving various NP-hard problems using exponentially fewer qubits on a quantum computer”. Phys. Rev. A 109, 052441 (2024)

2024
[12]

Noisy intermediate-scale quantum computing algorithm for solving an n-vertex maxcut problem with log(n) qubits

Marko J. Rančić. “Noisy intermediate-scale quantum computing algorithm for solving an n-vertex maxcut problem with log(n) qubits”. Phys. Rev. Res.5, L012021 (2023)

2023
[13]

Differential evolution - a simple and efficient heuris- tic for global optimization over continuous spaces

Rainer Storn and Kenneth Price. “Differential evolution - a simple and efficient heuris- tic for global optimization over continuous spaces”. Journal of Global Optimization 11, 341–359 (1997)

1997
[14]

A variational eigenvalue solver on a photonic quantum processor

Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man-Hong Yung, Xiao-Qi Zhou, Peter J. Love, Alán Aspuru-Guzik, and Jeremy L. O’Brien. “A variational eigenvalue solver on a photonic quantum processor”. Nature Communications5 (2014)

2014
[15]

Quantum variational optimization: The role of entanglement and problem hardness

Pablo Díez-Valle, Diego Porras, and Juan José García-Ripoll. “Quantum variational optimization: The role of entanglement and problem hardness”. Physical Review A104 (2021)

2021
[16]

A quantum approximate opti- mization algorithm

Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. “A quantum approximate opti- mization algorithm” (2014). arXiv:1411.4028

2014 arXiv
[17]

A review on quantum approximate optimization algorithm and its variants

Kostas Blekos, Dean Brand, Andrea Ceschini, Chiao-Hui Chou, Rui-Hao Li, Komal Pandya, and Alessandro Summer. “A review on quantum approximate optimization algorithm and its variants”. Physics Reports1068, 1–66 (2024)

2024
[18]

Approx- imate solutions of combinatorial problems via quantum relaxations

B. Fuller, C. Hadfield, J. R. Glick, T. Imamichi, T. Itoko, J. Richard Thompson, Y. Jiao, M. Marna Kagele, W. Adriana, R. Raymond, and A. Mezzacapo. “Approx- imate solutions of combinatorial problems via quantum relaxations”. IEEE Transac- tions on Quantum Engineering5, 1–15 (2024)

2024
[19]

Variational quantum optimization with multibasis encodings

Taylor Patti, Jean Kossaifi, Anima Anandkumar, and Susanne Yelin. “Variational quantum optimization with multibasis encodings”. Physical Review Research4 (2022)

2022
[20]

Towards large-scale quantum optimization solvers with few qubits

MarcoSciorilli, LucasBorges, TaylorL.Patti, DiegoGarcía-Martín, GiancarloCamilo, Anima Anandkumar, and Leandro Aolita. “Towards large-scale quantum optimization solvers with few qubits” (2024). arXiv:2401.09421

2024 arXiv
[21]

Quantum bridge analytics I: a tutorial on formulating and using QUBO models

Fred Glover, Gary Kochenberger, and Yu Du. “Quantum bridge analytics I: a tutorial on formulating and using QUBO models”. 4OR17 (2019)

2019
[22]

Ising formulations of many NP problems

Andrew Lucas. “Ising formulations of many NP problems”. Frontiers in Physics2, 5 (2014)

2014
[23]

Pseudo-boolean optimization

Endre Boros and Peter L. Hammer. “Pseudo-boolean optimization”. Discret. Appl. Math. 123, 155–225 (2002). url: https://api.semanticscholar.org/CorpusID: 11157651

2002
[24]

The interval analysis of multilin- ear expressions

Cosimo Laneve, Tudor A. Lascu, and Vania Sordoni. “The interval analysis of multilin- ear expressions”. Electronic Notes in Theoretical Computer Science267, 43–53 (2010)

2010
[25]

Barren plateaus in quantum neural network training landscapes

Jarrod R. McClean, Sergio Boixo, Vadim N. Smelyanskiy, Ryan Babbush, and Hart- mut Neven. “Barren plateaus in quantum neural network training landscapes”. Nature Communications 9 (2018). 25

2018
[26]

Modern computer arithmetic

Richard P. Brent and Paul Zimmermann. “Modern computer arithmetic”. Cambridge University Press. (2010)

2010
[27]

Approximate counting

Dominic Welsh. “Approximate counting”. Page 287–324. Cambridge University Press. (1997)

1997
[28]

Counting Unlabelled Subtrees of a Tree is #P- Complete

Leslie Ann and Goldberg Jerrum. “Counting Unlabelled Subtrees of a Tree is #P- Complete”. LMS Journal of Computation and Mathematics3 (2000)

2000
[29]

On the practical usefulness of the Hardware Efficient Ansatz

Lorenzo Leone, Salvatore F.E. Oliviero, Lukasz Cincio, and M. Cerezo. “On the practical usefulness of the Hardware Efficient Ansatz”. Quantum8, 1395 (2024)

2024
[30]

Evaluating analytic gradients on quantum hardware

Maria Schuld, Ville Bergholm, Christian Gogolin, Josh Izaac, and Nathan Killoran. “Evaluating analytic gradients on quantum hardware”. Phys. Rev. A99, 032331 (2019)

2019
[31]

Are- view of barren plateaus in variational quantum computing

Martin Larocca, Supanut Thanasilp, Samson Wang, Kunal Sharma, Jacob Biamonte, PatrickJ.Coles, LukaszCincio, JarrodR.McClean, ZoëHolmes, andM.Cerezo. “Are- view of barren plateaus in variational quantum computing” (2024). arXiv:2405.00781

2024 arXiv
[32]

TensorCir- cuit: a Quantum Software Framework for the NISQ Era

Shi-Xin Zhang, Jonathan Allcock, Zhou-Quan Wan, Shuo Liu, Jiace Sun, Hao Yu, Xing-Han Yang, Jiezhong Qiu, Zhaofeng Ye, Yu-Qin Chen, Chee-Kong Lee, Yi-Cong Zheng, Shao-Kai Jian, Hong Yao, Chang-Yu Hsieh, and Shengyu Zhang. “TensorCir- cuit: a Quantum Software Framework for the ...

2023
[33]

A limited memory algorithm for bound constrained optimization

Richard H. Byrd, Peihuang Lu, Jorge Nocedal, and Ciyou Zhu. “A limited memory algorithm for bound constrained optimization”. SIAM J. Sci. Comput. 16, 1190– 1208 (1995). url: https://api.semanticscholar.org/CorpusID:6398414

1995
[34]

The SCIP Optimization Suite 9.0

Suresh Bolusani, Mathieu Besançon, Ksenia Bestuzheva, Antonia Chmiela, João Dionísio, Tim Donkiewicz, Jasper van Doornmalen, Leon Eifler, Mohammed Ghan- nam, Ambros Gleixner, Christoph Graczyk, Katrin Halbig, Ivo Hedtke, Alexander Hoen, Christopher Hojny, Rolf van der Hulst, D...

2024
[35]

Quantum Optimization for the Graph Coloring Problem with Space-Efficient Embedding

Zsolt Tabi, Kareem H El-Safty, Zsófia Kallus, Péter Hága, Tamás Kozsik, Adam Glos, and Zoltán Zimborás. “Quantum Optimization for the Graph Coloring Problem with Space-Efficient Embedding”. In 2020 IEEE international conference on quantum computing and engineering (QCE). Pages...

2020
[36]

Graph coloring Instances

Michael Trick. “Graph coloring Instances”. url:https://mat.gsia.cmu.edu/COLOR/ instances.html. (accessed: 2024-03-25)

2024
[37]

An overview of the simultaneous perturbation method for efficient optimization

James C. Spall. “An overview of the simultaneous perturbation method for efficient optimization”. Johns Hopkins Apl Technical Digest19, 482–492 (1998). url: https: //api.semanticscholar.org/CorpusID:7988308

1998
[38]

IBM quantum

“IBM quantum”. url: https://quantum.ibm.com/. Accessed: 2024-12-12

2024
[39]

Practical optimization for hybrid quantum-classical algorithms

Gian Giacomo Guerreschi and Mikhail Smelyanskiy. “Practical optimization for hybrid quantum-classical algorithms” (2017). arXiv:1701.01450

2017 arXiv
[40]

Efficient optimization with higher-order ising machines

Connor Bybee, Denis Kleyko, Dmitri E. Nikonov, Amir Khosrowshahi, Bruno A. Ol- shausen, and Friedrich T. Sommer. “Efficient optimization with higher-order ising machines” (2022). arXiv:2212.03426

2022 arXiv
[41]

Lexicographic unranking of combinations revis- ited

Antoine Genitrini and Martin Pépin. “Lexicographic unranking of combinations revis- ited”. Algorithms 14, 97 (2021). 26

2021

Pith tools

Reviewed August 9, 2026 · model on record in the stance chip above.

[1] [1]

An efficient closed-form formula for evaluating r-flip moves in quadratic unconstrained binary optimization

Bahram Alidaee, Haibo Wang, and Lutfu S. Sua. “An efficient closed-form formula for evaluating r-flip moves in quadratic unconstrained binary optimization”. Algorithms 16, 557 (2023)

work page 2023

[2] [2]

Optimization by simulated annealing

S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi. “Optimization by simulated annealing”. Science 220, 671–680 (1983)

work page 1983

[3] [3]

Multistart tabu search strategies for the unconstrained binary quadratic optimization problem

Gintaras Palubeckis. “Multistart tabu search strategies for the unconstrained binary quadratic optimization problem”. Annals of Operations Research131, 259–282 (2004)

work page 2004

[4] [4]

Memetic algorithms for the unconstrained binary quadratic programming problem

Peter Merz and Kengo Katayama. “Memetic algorithms for the unconstrained binary quadratic programming problem”. Bio Systems78, 99–118 (2005)

work page 2005

[5] [5]

Metaheuristic algorithms

Yang Wang and Jin-Kao Hao. “Metaheuristic algorithms”. Pages 241–259. Springer International Publishing. Cham (2022)

work page 2022

[6] [6]

Quantum Local Search with the Quantum Alternating Operator Ansatz

Teague Tomesh, Zain H. Saleem, and Martin Suchara. “Quantum Local Search with the Quantum Alternating Operator Ansatz”. Quantum6, 781 (2022)

work page 2022

[7] [7]

Reinforcement learning quantum local search

Chen-Yu Liu and Hsi-Sheng Goan. “Reinforcement learning quantum local search”. In 2023 IEEE International Conference on Quantum Computing and Engineering (QCE). Page 246–247. IEEE (2023)

work page 2023

[8] [8]

Qubit-efficient encoding schemes for binary optimisation problems

Benjamin Tan, Marc-Antoine Lemonde, Supanut Thanasilp, Jirawat Tangpanitanon, 24 and Dimitris G. Angelakis. “Qubit-efficient encoding schemes for binary optimisation problems”. Quantum 5, 454 (2021)

work page 2021