Penalty-free quantum optimization applied to lattice protein folding

• URL: http://arxiv.org/abs/2606.02104v2
• Date: Tue, 02 Jun 2026 07:25:57 GMT
• Title: Penalty-free quantum optimization applied to lattice protein folding
• Abstract summary: We introduce an analog 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.<n>We validate this approach through classical simulations of the quantum circuits for lattice proteins of lengths $N=4$ and $N=6$.<n>To explore larger systems, we further introduce an 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.
• Score: 0.6999740786886536
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Verifiable quantum advantage in extremely low depth [52.51019642214249]
  We give a problem that is solvable by shallow quantum circuits, hard for computation in time under lattice-based assumptions.<n>We prove that shallow quantum circuits have sufficient structure to solve certain classically hard tasks whose solutions can be verified efficiently.
  arXiv  Detail & Related papers  (2026-09-01T15:54:34Z)
• SpinGQE: A Generative Quantum Eigensolver for Spin Hamiltonians [42.007194397302825]
  Ground state search is central to quantum computing.<n>We present SpinGQE, an extension of the Generative Quantum Eigensolver framework to spin Hamiltonians.<n>We employ a transformer-based decoder to learn over quantum circuits that produce low-energy states.
  arXiv  Detail & Related papers  (2026-03-25T13:38:15Z)
• Folding lattice proteins confined on minimal grids using a quantum-inspired encoding [0.0]
  Steric clashes pose a challenge when exploring dense protein systems.<n>Finding its minimum energy is a hard optimization problem.<n>We show that this problem in its QUBO form can be swiftly and consistently solved for chain length 48.
  arXiv  Detail & Related papers  (2025-10-02T10:58:31Z)
• Learning Feasible Quantum States for Quadratic Constrained Binary Optimization Problems [41.23247424467223]
  We develop a variational approach that creates an equal superposition of quantum states that satisfy constraints in a QCBO.<n>The resulting equal superposition can be used as an initial state for quantum algorithms that solve QUBOs/QCBOs.
  arXiv  Detail & Related papers  (2025-08-04T16:44:53Z)
• Max-Cut graph-driven quantum circuit design for planar spin glasses [0.0]
  We present a graph-based approach for finding the ground state of spin glasses.<n>We employ a clustering strategy that organizes qubits into distinct groups based on the maximum cut technique.<n>Our results underscore the potential of hybrid quantum-classical methods in addressing complex optimization problems.
  arXiv  Detail & Related papers  (2025-04-16T14:00:32Z)
• Reducing QUBO Density by Factoring Out Semi-Symmetries [4.581191399651181]
  We introduce the concept of textitsemi-symmetries in QUBO matrices.<n>We show that our algorithm reduces the number of couplings and circuit depth by up to $45%.
  arXiv  Detail & Related papers  (2024-12-18T12:05:18Z)
• Optimizing random local Hamiltonians by dissipation [44.99833362998488]
  We prove that a simplified quantum Gibbs sampling algorithm achieves a $Omega(frac1k)$-fraction approximation of the optimum. Our results suggest that finding low-energy states for sparsified (quasi)local spin and fermionic models is quantumly easy but classically nontrivial.
  arXiv  Detail & Related papers  (2024-11-04T20:21:16Z)
• Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
  We study the problem of estimating frequency response functions of systems of coupled, classical harmonic oscillators using a quantum computer.<n>Our proposed quantum algorithm operates in the standard $s-sparse, oracle-based query access model.<n>We show that a simple adaptation of our algorithm solves the random glued-trees problem in time.
  arXiv  Detail & Related papers  (2024-05-14T15:28:37Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• Coherent Equalization of Linear Quantum Systems [0.0]
  We find a near optimal equalizing filter which is itself a passive quantum system. An additional semidefinite relaxation combined with the Nevanlinna-Pick is shown to lead to a tractable algorithm for the design of a near optimal coherent equalizer.
  arXiv  Detail & Related papers  (2022-11-11T05:06:33Z)
• Analyzing Prospects for Quantum Advantage in Topological Data Analysis [35.423446067065576]
  We analyze and optimize an improved quantum algorithm for topological data analysis. We show that super-quadratic quantum speedups are only possible when targeting a multiplicative error approximation. We argue that quantum circuits with tens of billions of Toffoli can solve seemingly classically intractable instances.
  arXiv  Detail & Related papers  (2022-09-27T17:56:15Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits. Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit. We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
  arXiv  Detail & Related papers  (2022-06-30T03:15:23Z)
• Variational quantum solutions to the Shortest Vector Problem [6.126929553818864]
  Shortest Vector Problem (SVP) is a problem known as the Shortest Vector Problem (SVP) This problem is believed to be hard even on quantum computers and plays a pivotal role in post-quantum cryptography. In this work we explore how (efficiently) Noisy Intermediate Scale Quantum (NISQ) devices may be used to solve SVP.
  arXiv  Detail & Related papers  (2022-02-14T14:27:38Z)

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.