Scientific knowledge map · Paper #60
Quantum Optimization Heuristics with an Application to Knapsack Problems
2021 · IEEE International Conference on Quantum Computing and Engineering (QCE)
- Theory
- Applied
- algorithm
Research question
What does the paper try to establish?
Can shallow QAOA-style heuristics use a classical greedy solution to stay near feasible high-value regions of a constrained knapsack search space and outperform comparably simple classical heuristics?
Central answer
What is the proposed answer?
The paper initializes qubits from smoothed greedy marginals and introduces hourglass and copula mixers that preserve those biases while exploring nearby solutions. Statevector simulations on small hard-instance families report better performance than selected shallow classical baselines, with explicit classical-simulability and scaling caveats.
Evidence profile
Six dimensions, kept separate
The chart summarizes documented evidence and process. It is not a correctness probability, confidence score, or ranking, and no composite score is calculated.
LowMediumHighN/A = not assessed
A smaller value means less documented support for that dimension, not that the paper is false or unimportant.
- Epistemic evidence Medium
-
The algorithms are derived and evaluated systematically on five instance families with transparent baselines and caveats, but evidence is limited to small statevector simulations and does not establish scaling or quantum advantage.
Biased initial states, hourglass mixer, and copula mixer Classical comparison setup Simulation results and sensitivity Conclusions, limits, and future work - Auditability High
-
The complete checked-in archive copy has page count and SHA-256 and is linked to the official DOI; algorithms and experiment settings are explicit, though code and raw results are absent.
Motivation, contributions, and classical-simulability caveat Official IEEE QCE publication identity - Production provenance Medium
-
Authors, venue, versions, funding, algorithms, and experimental choices are documented; code revision, raw data, contributor roles, and tool versions are not.
Official IEEE QCE publication identity Five hard-instance distributions Simulation results and sensitivity - External scrutiny Medium
-
IEEE QCE publication establishes venue review, but review reports and independent reproduction are not represented.
Official IEEE QCE publication identity - Reception Low
-
The dated exact-DOI OpenAlex record located 4 citations. Under the author-defined rule, 0 through 8 located citations is Low; counts vary by index and date.
Dated citation-count snapshot - Contribution significance Medium
-
The bias-preserving and copula mixer constructions are reusable ideas for constrained optimization, but the paper itself rules out a quantum-advantage interpretation for one path and leaves scaling open.
Motivation, contributions, and classical-simulability caveat Conclusions, limits, and future work
Assessment: Ai draft author review pending · 2026-07-11 · rubric 0.2. These dimensions describe documented support and process, not truth, correctness, or a universal ranking. No composite score is calculated.
Top-down and bottom-up view
Hierarchical knowledge map
Collapse a branch for a top-level reading, or follow its source links and child nodes to audit the evidence and boundaries underneath it.
Quantum Optimization Heuristics with an Application to Knapsack Problems
Two biased QAOA-style optimization algorithms for constrained knapsack instances, analyzed algebraically and evaluated by small statevector simulations.
Motivation, contributions, and classical-simulability caveat-
question Research question
research questionCan a greedy warm start and bias-preserving mixers focus a shallow quantum search near feasible solutions without the qubit cost of penalty encodings?
Motivation, contributions, and classical-simulability caveat QAOA and penalty-function baseline -
contribution Central answer
simulated supportConvert a smoothed lazy-greedy profile into product-state qubit marginals, preserve those marginals with an hourglass mixer, and optionally add pairwise anticorrelation through a copula mixer.
Biased initial states, hourglass mixer, and copula mixer Knapsack-specific xQAOA design -
scope Experimental regime
explicitly scopedResults use binary knapsack instances with ten items, depth-one circuits, statevector simulation, ten output samples per algorithm run, and 100 instances from each of five selected hard distributions.
Five hard-instance distributions Quantum algorithms and parameter optimization Simulation results and sensitivity -
algorithm Biased xQAOA specified
A logistic smoothing of the lazy-greedy stopping ratio assigns each item a qubit inclusion probability, creating a constant-depth initial state near the capacity boundary rather than a uniform superposition.
Biased initial states, hourglass mixer, and copula mixer Knapsack-specific xQAOA design-
algorithm QKP hourglass mixer
specifiedA single-qubit mixer has each biased marginal state as an eigenstate, preserving the chosen product-distribution bias while the objective phase steers probability toward higher-value strings.
Biased initial states, hourglass mixer, and copula mixer Knapsack-specific xQAOA design -
algorithm QKP copula mixer
specifiedTwo-qubit copula operations preserve individual marginals while adding tunable correlations; the evaluated ring construction favors anticorrelation so neighboring items are less likely to be jointly selected.
Biased initial states, hourglass mixer, and copula mixer Knapsack-specific xQAOA design
-
-
evidence group Comparison design controlled simulation
Quantum heuristics are compared with lazy greedy, very greedy, warm-start simulated annealing, and a global one-step annealing variant on strongly correlated, inverse-strong, profit, and two spanner distributions.
Five hard-instance distributions Classical comparison setup-
method Parameter search
per instance optimizedQuantum angles are grid-searched then refined with BFGS for each instance across bias strengths and selected copula correlations; simulated annealing temperature is also tuned per instance from repeated trials.
Classical comparison setup Quantum algorithms and parameter optimization
-
-
claim Better results than selected shallow heuristics
simulation resultAcross the sampled ten-item instances, the hourglass variant typically exceeds the four chosen classical heuristics and the copula variant improves further; infeasible outputs count as zero rather than being postselected away.
Simulation results and sensitivity -
claim Limited sensitivity on the tested size
numerical observationThe tested copula mixer generally prefers maximal anticorrelation, performance varies weakly across the sampled bias strengths, and favorable beta angles cluster in two regions, suggesting some parameter reuse at n equals 10.
Simulation results and sensitivity -
limitation group Boundaries material
Experiments are statevector simulations at n equals 10 and depth one, use heavily optimized per-instance parameters, and compare only simple classical methods. The authors expect more elaborate classical algorithms to outperform these quantum heuristics and leave larger n, deeper p, and parameter-scaling behavior open.
Quantum algorithms and parameter optimization Simulation results and sensitivity Conclusions, limits, and future work-
limitation Hourglass path can be quantum-inspired classical
explicitly acknowledgedFor a linear objective such as knapsack, the first non-entangling technique can be classically simulated with comparable circuit complexity, so its improvement is not evidence of quantum advantage.
Motivation, contributions, and classical-simulability caveat Conclusions, limits, and future work
-
-
evidence group Evidence boundary
analytical and simulatedThe paper supplies circuit derivations, pseudocode, instance generators, baseline settings, scatter plots, and sensitivity results. It supplies neither hardware experiments nor a proof of asymptotic advantage.
Biased initial states, hourglass mixer, and copula mixer Five hard-instance distributions Simulation results and sensitivity -
artifact group Publication resources
source availableThe checked-in arXiv manuscript has fixity metadata and the DOI identifies the IEEE publication. No code or data artifact is represented in the paper map.
Motivation, contributions, and classical-simulability caveat Official IEEE QCE publication identity -
scrutiny External scrutiny
venue reviewedThe paper appeared at IEEE QCE 2021. Public review reports and independent experimental reproduction are not linked.
Official IEEE QCE publication identity -
lineage Warm-start constrained QAOA line
documentedThe work extends prior alternating-operator and warm-start approaches with constant-depth bias-preserving and copula mixers specialized and tested for knapsack.
Biased initial states, hourglass mixer, and copula mixer Conclusions, limits, and future work
Audit trail
Source index
Locators state the depth of the current audit. PDF page numbers, where present, are one-based file pages; metadata-, summary-, and abstract-bounded records explicitly identify their limitations.
- Motivation, contributions, and classical-simulability caveat Abstract and Sections 1-1.1, PDF pages 1-2
- QAOA and penalty-function baseline Section 2, PDF pages 2-3
- Biased initial states, hourglass mixer, and copula mixer Section 3, PDF pages 3-7
- Knapsack definition and classical baselines Section 4, PDF pages 7-9
- Knapsack-specific xQAOA design Section 5, PDF pages 9-11
- Five hard-instance distributions Section 6.1, PDF pages 11-12
- Classical comparison setup Section 6.2, PDF pages 12-13
- Quantum algorithms and parameter optimization Sections 6.3.1-6.3.2, PDF pages 13-15
- Simulation results and sensitivity Sections 6.3.3-6.3.4, PDF pages 15-16
- Conclusions, limits, and future work Section 7, PDF page 18
- Official IEEE QCE publication identity DOI 10.1109/QCE52317.2021.00033
- Dated citation-count snapshot OpenAlex reported 4 citations when accessed 2026-07-11