Quantum feedback algorithms for DNA assembly using FALQON variants

Titel: Quantum feedback-algoritmen voor DNA-assembly met FALQON-varianten

Auteurs: Pedro M. Prado et al.
Datum: 25 februari 2026

1. Probleemstelling: De novo DNA-assembly

Het reconstructeren van DNA-sequenties zonder gebruik van een referentie (bekend als de novo assembly) is een complexe computationele taak. De uitdaging ligt in het optimaal uitlijnen van overlappende fragmenten (reads) die gegenereerd zijn door high-throughput sequencing.

• Complexiteit: Genomische herhalingen, sequencing-fouten en de enorme hoeveelheid data maken dit probleem moeilijk op te lossen met klassieke methoden (zoals de Bruijn-graafbenaderingen), die vaak beperkingen hebben in schaalbaarheid en nauwkeurigheid.
• Formulering: Het probleem kan worden gemodelleerd als een Quadratic Unconstrained Binary Optimization (QUBO) probleem. Dit wordt gedaan door de assembly te zien als een Traveling Salesman Problem (TSP) op een graaf, waarbij de randen de kosten van overlappingen vertegenwoordigen. Het doel is het vinden van een Hamilton-cyclus die de totale overlap maximaliseert (of de kosten minimaliseert).
• Kwantumtoepassing: Het QUBO-probleem wordt omgezet in een Ising-Hamiltoniaan, wat geschikt is voor oplossing via kwantumalgoritmen.

2. Methodologie

De auteurs onderzoeken drie varianten van het FALQON-algoritme (Feedback-based Algorithm for Quantum Optimization). In tegenstelling tot variatiealgoritmen zoals QAOA, die een klassieke optimalisatielus vereisen om parameters te vinden (wat gevoelig is voor ruis en "barren plateaus" op NISQ-hardware), elimineert FALQON deze klassieke lus volledig.

• FALQON (Standaard):

  • Gebruikt meetresultaten (feedback) om de circuitparameters dynamisch bij te werken.
  • Gebaseerd op Lyapunov-controle: de verwachte energie $\langle H_p \rangle$ moet monotoon dalen.
  • De parameter $\beta_k$ wordt bij elke laag bijgewerkt op basis van de verwachtingswaarde van de commutator tussen de driver-Hamiltoniaan ($H_d$) en de probleem-Hamiltoniaan ($H_p$): $\beta_{k+1} = -i\langle \psi_k | [H_d, H_p] | \psi_k \rangle$.

• TR-FALQON (Time-Rescaled FALQON):

  • Introduceert een tijdsrescaling-functie $f(\tau)$ om de evolutie te versnellen of te vertragen.
  • Dit stelt het algoritme in staat om sneller te convergeren in ondiepe circuits (klein aantal lagen), wat cruciaal is voor huidige kwantumhardware met beperkte coherentietijd.
  • De feedbackwet wordt aangepast met een schalingsfactor $\dot{f}(\tau)$.

• SO-FALQON (Second-Order FALQON):

  • Gebruikt een tweede-orde Taylor-expansie van de evolutie-operatoren.
  • Hierdoor worden kwadratische termen in de feedbackwet meegenomen, wat grotere stapgroottes toelaat en de convergentie versnelt.
  • Het algoritme kiest adaptief tussen een eerste-orde en tweede-orde update om stabiliteit en snelheid te balanceren.

Experimenteel Opzet:

• Data: Lange reads van SARS-CoV-2 en menselijk mitochondriaal DNA.
• Implementatie: Python met PyTorch.
• Schaal: Experimenten uitgevoerd met 4, 5 en 6 reads, wat resulteert in QUBO-problemen die 9, 16 en 25 qubits vereisen (na fixatie van de eerste read).

3. Belangrijkste Bijdragen

1. Toepassing op Biologie: Eerste toepassing van FALQON-varianten specifiek voor het de novo assembly van DNA, gemodelleerd als een QUBO/Ising-probleem.
2. Eliminatie van Klassieke Lussen: Demonstratie dat feedback-gedreven kwantumdynamica effectief is voor combinatorische optimalisatie zonder de noodzaak van klassieke parameteroptimalisatie.
3. Verbeterde Varianten: Introductie en validatie van TR-FALQON en SO-FALQON, die specifiek zijn ontworpen om de beperkingen van NISQ-apparaten (ruis, beperkte circuitdiepte) te overwinnen.
4. Benchmarking: Uitgebreide numerieke vergelijking tussen de drie methoden op realistische biologische datasets.

4. Resultaten

De numerieke simulaties tonen aan dat de varianten superieur presteren aan het standaard FALQON:

• Convergentie: Zowel TR-FALQON als SO-FALQON convergeren sneller naar de grondtoestand (ground state) dan het standaard FALQON.
• Circuitdiepte: De varianten bereiken hoge successkansen met aanzienlijk minder circuitlagen. Dit is essentieel voor huidige kwantumcomputers waar diepe circuits leiden tot onacceptabele ruis.
• Succeskans:
  • TR-FALQON (met mildere hyperparameters) bereikte de laagste eindenergie en een successkans van meer dan 50%.
  • TR-FALQON (agressieve parameters) convergeerde het snelst (minste lagen), hoewel de kans op meting van de oplossing rond de 40% stabiliseerde.
  • SO-FALQON toonde robuustheid en stabiliteit, zelfs bij grotere tijdsintervallen.
• Schaalbaarheid: De voordelen van de varianten worden duidelijker naarmate het aantal reads (en dus de complexiteit van het probleem) toeneemt.

5. Betekenis en Conclusie

Dit werk bevestigt dat feedback-gedreven kwantumalgoritmen een veelbelovende richting zijn voor het oplossen van combinatorische problemen op toekomstige kwantumhardware.

• NISQ-Compatibiliteit: Door de noodzaak van klassieke optimalisatie te elimineren en de circuitdiepte te verminderen via tijdsrescaling en tweede-orde correcties, zijn deze methoden beter geschikt voor de huidige generatie kwantumprocessors.
• Biomedische Toepassing: Het succes bij het assembleren van SARS-CoV-2 en mitochondriaal DNA suggereert dat deze aanpak schaalbaar kan zijn voor complexere genomische taken, wat bijdraagt aan snellere diagnostiek en het begrijpen van genetische variatie.
• Toekomst: De resultaten onderstrepen het potentieel van feedback-algoritmen voor grootschalige bio-informatica-taken, waarbij de beperkingen van ruis en coherentie tijd een centrale rol spelen.

Kortom, de auteurs tonen aan dat geavanceerde feedbackstrategieën (TR- en SO-FALQON) de efficiëntie en haalbaarheid van kwantumoplossingen voor DNA-assembly aanzienlijk verbeteren ten opzichte van bestaande methoden.