pith. sign in

arxiv: 2606.02104 · v2 · pith:TPY6J3PQnew · submitted 2026-06-01 · 🪐 quant-ph · physics.bio-ph· physics.comp-ph

Penalty-free quantum optimization applied to lattice protein folding

Leif Gellersen , Anders Irb\"ack , Lucas Knuthson , Stefan Prestel This is my paper

Pith reviewed 2026-06-28 14:33 UTC · model grok-4.3

classification 🪐 quant-ph physics.bio-phphysics.comp-ph
keywords lattice protein foldingQAOAindependent setsconflict graphpenalty-freequantum optimizationprotein energy minimization
0
0 comments X

The pith

A quantum algorithm solves lattice protein folding without penalty terms by using independent sets of a conflict graph.

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

The paper establishes that lattice protein folding can be mapped to a quantum approximate optimization problem without quadratic penalty terms. Valid chain configurations are enforced by restricting the search space to independent sets in a conflict graph and applying a QAOA mixer designed for the maximum independent set problem. This leaves an objective function consisting only of the protein energy plus a linear bias term. The approach is tested through classical circuit simulations on proteins of length 4 and 6, and extended via a heuristic local-search method on subgraphs to reach lengths up to 14.

Core claim

By constructing a conflict graph whose independent sets correspond exactly to valid lattice protein configurations, and employing a QAOA mixer designed for the maximum independent set problem, the folding problem can be solved with an objective consisting solely of the protein energy and a linear bias term. This approach is validated on proteins of length 4 and 6 via direct simulation and extended to length 14 using an iterative local-search heuristic on local subgraphs.

What carries the argument

The QAOA mixer for the maximum independent set problem applied to the conflict graph of lattice configurations, which enforces validity without penalties.

If this is right

  • Proteins up to length 14 can be folded using this method with local subgraphs of at most 26 qubits.
  • The objective function avoids quadratic penalties, consisting only of energy plus linear bias.
  • Direct classical simulation succeeds for N=4 and N=6.
  • The method identifies minimum-energy structures for the tested lattice proteins.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Similar penalty-free mappings could simplify quantum optimization for other discrete problems with configuration constraints.
  • The local-search heuristic on subgraphs may generalize to larger systems if subgraph size can be controlled.
  • This reduces the complexity of the cost function, potentially improving performance on near-term quantum devices.

Load-bearing premise

The conflict graph must be constructed so that its independent sets include every valid chain configuration, including those with low energy, without any omissions.

What would settle it

Finding a known low-energy valid fold for a length-14 protein that the algorithm fails to discover would falsify the claim that the method reliably identifies global minima.

Figures

Figures reproduced from arXiv: 2606.02104 by Anders Irb\"ack, Leif Gellersen, Lucas Knuthson, Stefan Prestel.

Figure 1
Figure 1. Figure 1: FIG. 1. Folding the sequence HPPH on a 3 [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: FIG. 2. Full-length chain structures corresponding to states labeled I [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: FIG. 3. (Left) Conflict graph for the sequence HPPH on a 3 [PITH_FULL_IMAGE:figures/full_fig_p011_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: FIG. 4. Success probability, defined as the squared overlap with the known ground state, as a [PITH_FULL_IMAGE:figures/full_fig_p013_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: FIG. 5. Success probability, defined as the squared overlap with the known ground state, as a [PITH_FULL_IMAGE:figures/full_fig_p015_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: FIG. 6. (a) Fractions of correct and incorrect solutions in runs with the QLS approach described [PITH_FULL_IMAGE:figures/full_fig_p016_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: FIG. 7. Local neighborhood sizes in our QLS computations (Secs. [PITH_FULL_IMAGE:figures/full_fig_p018_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: FIG. 8. Minimum-energy structures [ [PITH_FULL_IMAGE:figures/full_fig_p021_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: FIG. 9. Energy landscapes [PITH_FULL_IMAGE:figures/full_fig_p022_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: FIG. 10. Energy landscapes [PITH_FULL_IMAGE:figures/full_fig_p022_10.png] view at source ↗
read the original abstract

Identifying minimum-energy structures of lattice proteins is a challenging discrete optimization problem. Quantum approaches such as analog quantum annealing and the gate-based quantum approximate optimization algorithm (QAOA) can address this problem after mapping it to a binary representation, which typically involves introducing penalty terms to enforce valid chain configurations. However, in this and many related problems, the use of quadratic penalty terms can be avoided by restricting the search space to independent sets in a conflict graph and using a QAOA mixer designed for the maximum independent set problem. In this work, we implement and explore this QAOA variant for lattice protein folding. Here, the objective function consists solely of the protein energy together with a simple linear bias term, without quadratic penalties. We validate this approach through classical simulations of the quantum circuits for lattice proteins of lengths $N=4$ and $N=6$. To explore larger systems, we further introduce a heuristic iterative local-search scheme, with which we successfully fold lattice proteins with lengths up to $N=14$ using local subgraphs with at most 26 qubits.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper claims that a QAOA variant for the maximum independent set problem on a conflict graph allows penalty-free optimization of lattice protein folding, with the objective consisting only of the protein energy plus a linear bias. Classical simulations validate the approach for N=4 and N=6; a heuristic iterative local-search scheme on local subgraphs (≤26 qubits) is then used to report successful folding for proteins up to N=14.

Significance. If the heuristic reliably locates global minima, the work provides a concrete demonstration that validity constraints can be enforced via the mixer and search space restriction rather than quadratic penalties, which is a useful technical contribution for constrained quantum optimization. The small-N circuit simulations supply direct evidence for the mapping; the N=14 results, however, rest on an unproven assumption about the local-search procedure.

major comments (2)
  1. [heuristic iterative local-search scheme paragraph] The section introducing the heuristic iterative local-search scheme (the paragraph beginning 'To explore larger systems...'): the manuscript reports that this procedure 'successfully fold[s] lattice proteins with lengths up to N=14', yet provides no exhaustive verification, known-optima comparison, or convergence argument showing that the scheme reaches the global minimum-energy valid configuration rather than a higher-energy local minimum. This assumption is load-bearing for the central claim that the method solves the problem for N=14.
  2. [conflict graph construction paragraph] The description of conflict-graph construction (the paragraph on restricting the search space to independent sets): while the text states that independent sets 'exactly correspond to all valid chain configurations', no explicit check or enumeration is supplied confirming that every low-energy valid fold is retained and that no valid configurations are inadvertently excluded by the conflict edges. This is required to ensure the reported energies are comparable to the true ground states.
minor comments (2)
  1. [abstract and results] The abstract and results section would benefit from explicit reporting of circuit depths, approximation ratios achieved, and direct baseline comparisons (e.g., against classical solvers or penalty-based QAOA) for the N=4 and N=6 cases.
  2. [objective function definition] Notation for the linear bias term and the precise form of the objective function should be introduced with an equation number for clarity when first presented.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful reading and valuable comments on our manuscript. We address each major comment below and indicate the revisions we will make.

read point-by-point responses

  1. Referee: The section introducing the heuristic iterative local-search scheme (the paragraph beginning 'To explore larger systems...'): the manuscript reports that this procedure 'successfully fold[s] lattice proteins with lengths up to N=14', yet provides no exhaustive verification, known-optima comparison, or convergence argument showing that the scheme reaches the global minimum-energy valid configuration rather than a higher-energy local minimum. This assumption is load-bearing for the central claim that the method solves the problem for N=14.

    Authors: We agree that the iterative local-search procedure is a heuristic and that exhaustive verification of global optimality is infeasible for N=14 due to the size of the configuration space. The manuscript presents the lowest energies obtained by this procedure on local subgraphs and notes their competitiveness with classical results where available. We will revise the relevant sections to explicitly describe the method as heuristic, clarify that global optimality is not guaranteed, and add a discussion of its limitations along with any available comparisons to known ground-state energies for the proteins studied. This addresses the load-bearing nature of the assumption while preserving the demonstration that the penalty-free QAOA mapping can be applied at these sizes via the heuristic. revision: partial

  2. Referee: The description of conflict-graph construction (the paragraph on restricting the search space to independent sets): while the text states that independent sets 'exactly correspond to all valid chain configurations', no explicit check or enumeration is supplied confirming that every low-energy valid fold is retained and that no valid configurations are inadvertently excluded by the conflict edges. This is required to ensure the reported energies are comparable to the true ground states.

    Authors: The conflict graph is constructed by placing an edge between any two nodes whose simultaneous selection would violate chain connectivity or self-avoidance; therefore, by definition, every independent set encodes a valid lattice configuration and no valid configuration is excluded. For the N=4 and N=6 cases we have performed full enumeration within the QAOA simulations, confirming that all valid folds are retained. We will add an explicit paragraph (or small worked example) detailing this construction and the resulting bijection to make the correspondence rigorous and transparent. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained

full rationale

The paper maps lattice protein folding to a maximum independent set problem on a conflict graph, applies a standard QAOA mixer for that problem, and uses an objective consisting only of the protein energy plus a linear bias term. Validation for N=4 and N=6 is performed via direct classical simulation of the circuits. The extension to N=14 relies on an explicitly introduced heuristic iterative local-search procedure on subgraphs; this is presented as a practical exploration tool rather than a derived claim that reduces to fitted parameters or prior self-citations. No equations or steps in the provided text equate a prediction to its own inputs by construction, and no load-bearing uniqueness theorems or ansatzes are imported via self-citation. The central construction therefore remains independent of the target results.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Based on abstract only; no free parameters, invented entities, or non-standard axioms are described. Relies on established QAOA and graph theory.

axioms (1)
  • standard math The standard QAOA framework and mixer for the maximum independent set problem can be directly applied to the protein folding objective after graph mapping.
    Invoked implicitly when describing the penalty-free objective and mixer design.

pith-pipeline@v0.9.1-grok · 5723 in / 1402 out tokens · 32208 ms · 2026-06-28T14:33:48.127019+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

40 extracted references · 7 canonical work pages · 5 internal anchors

  1. [1]

    We first randomly select a root node, (i 0, n0)

    Selection ofC loc. We first randomly select a root node, (i 0, n0). We then add every one of its neighbors that can be included without extending the search to states that are unfeasible due to conflicts with surrounding nodes (see above). We restrict our- selves to first neighbors to keep the quantum circuit computationally manageable. An illustration of...

  2. [2]

    The pinning status is updated based on the out- come of the preceding local search

    Pinning/unpinning of amino acids. The pinning status is updated based on the out- come of the preceding local search. Any amino acidifor whichb i,n changed from 0 to 1 for somenbecomes pinned with probabilityp p. Any amino acid that was already pinned is unpinned with probabilityp u. In the computations presented below, these parameters are set top p = 0....

  3. [3]

    The initial state|ψ 0⟩(Eq

    QAOA MIS-based minimization ofE MIS over unpinned amino acids inC loc. The initial state|ψ 0⟩(Eq. 2.6) is chosen to be a product of single-qubit states,|ψ i,n⟩. We set |ψi,n⟩=|0⟩ifb i,n = 0. Ifb i,n = 1, we set|ψ i,n⟩= 2 −1/2 (|0⟩+|1⟩) rather than |ψi,n⟩=|1⟩, to facilitate escape from local minima. When testing this scheme for QAOA MIS-based iterative loc...

    work page doi:10.1007/bf01994876

  4. [4]

    Kadowaki and H

    T. Kadowaki and H. Nishimori, Phys. Rev. E58, 5355 (1998)

    1998

  5. [5]

    A Quantum Approximate Optimization Algorithm

    E. Farhi, J. Goldstone, and S. Gutmann, arXiv:1411.4028 (2014), 10.48550/arXiv.1411.4028

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.1411.4028 2014

  6. [6]

    Hadfield, Z

    S. Hadfield, Z. Wang, B. O’Gorman, E. G. Rieffel, D. Venturelli, and R. Biswas, Algorithms 12, 34 (2019)

    2019

  7. [7]

    Hen and F

    I. Hen and F. M. Spedalieri, Phys. Rev. Appl.5, 034007 (2016)

    2016

  8. [8]

    Z. Wang, N. C. Rubin, J. M. Dominy, and E. G. Rieffel, Phys. Rev. A101, 012320 (2020)

    2020

  9. [9]

    Perdomo-Ortiz, N

    A. Perdomo-Ortiz, N. Dickson, M. Drew-Brook, G. Rose, and A. Aspuru-Guzik, Sci. Rep.2, 248 (2012)

    2012

  10. [10]

    Irb¨ ack, L

    A. Irb¨ ack, L. Knuthson, S. Mohanty, and C. Peterson, Phys. Rev. Res.4, 043013 (2022)

    2022

  11. [11]

    A quantum alternating operator ansatz with hard and soft constraints for lattice protein folding

    M. Fingerhuth, T. Babej, and C. Ing, arXiv:1810.13411 (2018), 10.48550/arXiv.1810.13411

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.1810.13411 2018

  12. [12]

    Boulebnane, X

    S. Boulebnane, X. Lucas, A. Meyder, S. Adaszewski, and A. Montanaro, npj Quantum Inf. 9, 70 (2023)

    2023

  13. [13]

    Robert, P

    A. Robert, P. K. Barkoutsos, S. Woerner, and I. Tavernelli, npj Quantum Inf.7, 38 (2021)

    2021

  14. [14]

    J. V. Pamidimukkala, S. Bopardikar, A. Dakshinamoorthy, A. Kannan, K. Dasgupta, and S. Senapati, J. Chem. Theory Comput.20, 10223 (2024)

    2024

  15. [15]

    Irb¨ ack, L

    A. Irb¨ ack, L. Knuthson, and S. Mohanty, Phys. Rev. E112, 045302 (2025)

    2025

  16. [16]

    V. K. Mulligan, H. Melo, H. I. Merritt, S. Slocum, B. D. Weitzner, A. M. Watkins, P. D. Renfrew, C. Pleasure, P. S. Arora, and R. Bonneau, bioRxiv:752485 (2020), 10.1101/752485

    work page doi:10.1101/752485 2020

  17. [17]

    Irb¨ ack, L

    A. Irb¨ ack, L. Knuthson, S. Mohanty, and C. Peterson, Phys. Rev. Res.6, 013162 (2024)

    2024

  18. [18]

    Panizza, P

    V. Panizza, P. Hauke, C. Micheletti, and P. Faccioli, PRX Life2, 043012 (2024)

    2024

  19. [19]

    H. Linn, L. Knuthson, A. Irb¨ ack, S. Mohanty, L. Garc´ ıa- ´Alvarez, and G. Johansson, arXiv:2508.02369 (2025), 10.48550/arXiv:2508.02369

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv:2508.02369 2025

  20. [20]

    Tomesh, Z

    T. Tomesh, Z. H. Saleem, and M. Suchara, Quantum6, 781 (2022)

    2022

  21. [21]

    Z. H. Saleem, T. Tomesh, B. Tariq, and M. Suchara, SN Comput. Sci.4, 183 (2023)

    2023

  22. [22]

    K. F. Lau and K. A. Dill, Macromolecules22, 3986 (1989)

    1989

  23. [23]

    K. Yue, K. M. Fiebig, P. D. Thomas, H. S. Chan, E. I. Shakhnovich, and K. A. Dill, Proc. Natl. Acad. Sci. USA92, 325 (1995)

    1995

  24. [24]

    H. Linn, I. Brundin, L. Garc´ ıa-´Alvarez, and G. Johansson, Phys. Rev. Res.6, 033112 (2024). 23

    2024

  25. [25]

    McGeoch, P

    C. McGeoch, P. Farr´ e, and W. Bernoudy,D-Wave Hybrid Solver Service + Advantage: tech- nology update, Tech. Rep. (D-Wave Systems Inc., 2020)

    2020

  26. [26]

    Irb¨ ack and C

    A. Irb¨ ack and C. Troein, J. Biol. Phys.28, 1 (2002)

    2002

  27. [27]

    Holzgr¨ afe, A

    C. Holzgr¨ afe, A. Irb¨ ack, and C. Troein, J. Chem. Phys.135, 195101 (2011)

    2011

  28. [28]

    Crescenzi, D

    P. Crescenzi, D. Goldman, C. Papadimitriou, A. Piccolboni, and M. Yannakakis, J. Comput. Biol.5, 423 (1998)

    1998

  29. [29]

    Bucher, J

    D. Bucher, J. Stein, S. Feld, and C. Linnhoff-Popien, Phys. Rev. A112, 062605 (2025)

    2025

  30. [30]

    B¨ artschi and S

    A. B¨ artschi and S. Eidenbenz, inFundamentals of Computation Theory, edited by L. A. G¸ asieniec, J. Jansson, and C. Levcopoulos (Springer, Cham, 2019) pp. 126–139

    2019

  31. [31]

    Zhou, S.-T

    L. Zhou, S.-T. Wang, S. Choi, H. Pichler, and M. D. Lukin, Phys. Rev. X10, 021067 (2020)

    2020

  32. [32]

    Quantum computing with Qiskit

    A. Javadi-Abhari, M. Treinish, K. Krsulich, C. J. Wood, J. Lishman, J. Gacon, S. Mar- tiel, P. D. Nation, L. S. Bishop, A. W. Cross, B. R. Johnson, and J. M. Gambetta, arXiv:2405.08810 (2024), 10.48550/arXiv.2405.08810

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.2405.08810 2024

  33. [33]

    Virtanen, R

    P. Virtanen, R. Gommers, T. E. Oliphant, M. Haberland, T. Reddy, D. Cournapeau, E. Burovski, P. Peterson, W. Weckesser, J. Bright, S. J. van der Walt, M. Brett, J. Wil- son, K. J. Millman, N. Mayorov, A. R. J. Nelson, E. Jones, R. Kern, E. Larson, C. J. Carey, ˙I. Polat, Y. Feng, E. W. Moore, J. VanderPlas, D. Laxalde, J. Perktold, R. Cimrman, I. Hen- rik...

    2020

  34. [34]

    Boppana and M

    R. Boppana and M. Halld´ orsson, BIT32, 180 (1992)

    1992

  35. [35]

    A. J. da Silva and D. K. Park, Phys. Rev. A106, 042602 (2022)

    2022

  36. [36]

    Zindorf and S

    B. Zindorf and S. Bose, Phys. Rev. Appl.24, 044030 (2025)

    2025

  37. [37]

    J. J. Hopfield and D. W. Tank, Biol. Cybern.52, 141 (1985)

    1985

  38. [38]

    Lucas, Front

    A. Lucas, Front. Phys.2, 1 (2014)

    2014

  39. [39]

    Quantum Annealing Implementation of Job-Shop Scheduling

    D. Venturelli, D. J. J. Marchand, and G. Rojo, arXiv:1506.08479 (2015), 10.48550/arXiv.1506.08479

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.1506.08479 2015

  40. [40]

    Vikst˚ al, M

    P. Vikst˚ al, M. Gr¨ onkvist, M. Svensson, M. Andersson, G. Johansson, and G. Ferrini, Phys. Rev. Appl.14, 034009 (2020). 24

    2020