Technische Samenvatting: Kwantumversnellingen voor Lineaire Programmering via Interior Point Methods

Probleemstelling

Het artikel behandelt de fundamentele taak van het oplossen van lineaire programma's (LP's) van de vorm $\min c^T x$ onder de voorwaarde $Ax \geq b$, waarbij $A \in \mathbb{R}^{n \times d}$, $b \in \mathbb{R}^n$ en $c \in \mathbb{R}^d$. De focus ligt specifts op "hoge" (tall) lineaire programma's waarbij het aantal ongelijkheidsbeperkingen $n$ aanzienlijk groter is dan het aantal variabelen $d$ ($n \gg d$).

Hoewel klassieke Interior Point Methods (IPM's) de state-of-the-art zijn voor het oplossen van LP's, is hun complexiteit voor hoge, dichte instanties ongeveer $\tilde{O}(nd + d^{2.5})$. De auteurs onderzoeken of kwantumalgoritmen een versnelling kunnen bieden voor IPM's in dit regime, met als doel een runtime die sublineair is ten opzichte van de inputgrootte (specifiek sublineair in $n$).

Methodologie

De voorgestelde aanpak is een kwantum interior point methode die de Newton-stap in de kern van de IPM-iteratie benadert. In plaats van exacte Hessianen en gradiënten te berekenen, maakt het algoritme gebruik van kwantumsubroutines om spectrale benaderingen van de Hessian en benaderingen van de gradiënt in de inverse-lokale norm te verkrijgen.

De methodologie rust op drie primaire kwantumcomponenten:

1. Kwantum Spectrale Benadering:
   Het algoritme construeert een spectrale benadering van een matrix $B^T B$ waarbij $B \in \mathbb{R}^{n \times d}$ een hoge matrix is. Dit wordt bereikt met een "repeated halving" strategie gecombineerd met leverage score sampling.

   • Mechanisme: Het algoritme gebruikt Grover-zoekopdrachten om belangrijke rijen te identificeren onder de $n$ rijen van $B$ in $\tilde{O}(\sqrt{n})$ queries, in plaats van $\tilde{O}(n)$ die klassiek vereist is.
   • Bootstrapping: Om de circulaire afhankelijkheid te vermijden waarbij het nodig is om leverage scores te gebruiken om rijen te samplen (wat $B^T B$ vereist), passen de auteurs een klassieke bootstrapping-techniek (Cohen et al.) aan naar de kwantumsetting. Ze gebruiken een keten van uniform gedownsamplde matrices om iteratief gegeneraliseerde leverage scores te schatten, die vervolgens worden gebruikt om de sampling te wegen.

2. Kwantum Benadering van Lewis Weights:
   Voor geavanceerde barrières (Volumetric en Lewis weight barriers) moet het algoritme $\ell_p$-Lewis weights benaderen.

   • Mechanisme: Lewis weights worden gedefinieerd via een fixed-point vergelijking die gebruikmaakt van de leverage scores van een geschaalde matrix. De auteurs implementeren een iteratief kwantumalgoritme gebaseerd op een low-precision klassiek algoritme (Apers, Gribling, en Sidford).
   • Efficiëntie: Omdat het expliciet opschrijven van $n$ gewichten te duur is voor sublineaire tijd, onderhoudt het algoritme impliciete datastructuren die efficiënte queries van tussenliggende gewichten mogelijk maken zonder volledige materialisatie.

3. Kwantum Gradiënt Benadering (Matrix-Vector Product):
   Het algoritme benadert de gradiënt $g(x)$ in de "inverse-lokale norm" $\|\cdot\|_{H(x)^{-1}}$.

   • Mechanisme: De gradiënt wordt beschouwd als het gemiddelde van een willekeurige variabele. De auteurs maken gebruik van een recent kwantumalgoritme voor multivariate gemiddelde-schatting (Cornelissen, Hamoudi, en Jerbi).
   • Preconditioning: Om afhankelijkheid van de conditiegetal van de Hessian te vermijden, construeert het algoritme eerst een spectrale benadering $\tilde{H}$ van de Hessian. Het sample vervolgens uit een "gepreconditioneerde" willekeurige variabele met behulp van $\tilde{H}^{-1/2}$, waardoor de trace van de covariantie-matrix gecontroleerd blijft en de resulterende estimator aan de vereiste normgrens voldoet.

Belangrijkste Bijdragen

1. Kwantum Spectrale Benaderingsalgoritme:
   Het artikel presenteert een kwantumalgoritme dat een $\delta$-spectrale benadering van $B^T B$ teruggeeft voor een hoge matrix $B$ met behulp van $\tilde{O}(\sqrt{nd}/\delta)$ rij-queries. Dit generaliseert eerdere kwantum graf-sparsificatie resultaten naar hoge matrices en bereikt een kwadratische versnelling ten opzichte van de klassieke $\tilde{O}(n)$ query lower bound voor deze specifieke taak.

2. Kwantum Lewis Weight Berekening:
   De auteurs ontwikkelen een kwantumalgoritme dat query-toegang biedt tot $\epsilon$-multiplicatieve benaderingen van $\ell_p$-Lewis weights. Dit omvat een preprocessing fase met $\tilde{O}(\sqrt{n} d^{7/2})$ queries en staat daaropvolgende queries toe met sublineaire kosten, wat het gebruik van Lewis weight barrières in een sublineaire kwantumsetting mogelijk maakt.

3. Robuustheid van IPM's tegen Benaderingen:
   Het artikel stelt formeel vast dat IPM's gebaseerd op self-concordant barrières (Logaritmisch, Volumetrisch en Lewis weight) robuust blijven wanneer de Newton-stap wordt geïmplementeerd met benaderde Hessianen en gradiënten. Specifiek wordt aangetoond dat spectrale benaderingen van de Hessian en benaderingen van de gradiënt in de inverse-lokale norm voldoende zijn om de convergentiegaranties te handhaven.

4. Kwantum IPM voor Hoge LP's:
   Door de bovenstaande subroutines te combineren, construeren de auteurs een kwantum IPM die hoge LP's oplost met $n$ beperkingen en $d$ variabelen.

   • Complexiteit: Voor de Lewis weight barrier draait het algoritme in tijd $\tilde{O}(\sqrt{n} \cdot \text{poly}(d, \log(1/\epsilon)))$.
   • Query Complexiteit: Het algoritme maakt $\tilde{O}(\sqrt{n} d^5)$ rij-queries naar de inputdata. Dit is sublineair in $n$ wanneer $n \gg d^{10}$.

Resultaten

Het artikel biedt de volgende theoretische resultaten:

• Theorem 1.1 (Hoofdresultaat): Er bestaat een kwantum IPM die een haalbare oplossing $\tilde{x}$ teruggeeft zodanig dat $c^T \tilde{x} \leq \text{val} + \epsilon$.

  • Voor de Logaritmische barrière: $\tilde{O}(nd)$ queries.
  • Voor de Volumetrische barrière: $\tilde{O}(n^{3/4} d^{5/4})$ queries.
  • Voor de Lewis weight barrière: $\tilde{O}(\sqrt{n} d^5)$ queries.
  • De tijdscomplexiteit voor de Lewis weight barrière is $\tilde{O}(\sqrt{n} \cdot \text{poly}(d))$.

• Lower Bounds:

  • Het artikel bewijst dat elk kwantumalgoritme voor spectrale benadering van $A^T A$ $\Omega(\sqrt{nd})$ rij-queries vereist, wat aangeeft dat de $\sqrt{n}$ afhankelijkheid in hun algoritme optimaal is.
  • Het reproduceert een lower bound die aantoont dat het oplossen van LP's tot constante precisie $\Omega(\sqrt{nd})$ kwantum queries (of $\Omega(n)$ klassieke queries) vereist, wat suggereert dat de $d$-afhankelijkheid in hun algoritme het primaire gebied is voor potentiële verbetering.

• Vergelijking met Benchmarks:

  • De auteurs vergelijken hun resultaat met een kwantumversnelling gebaseerd op cutting plane methoden (gebruikmakend van Grover-zoekopdrachten op een separation oracle), die $\tilde{O}(\sqrt{n} d)$ queries bereikt.
  • Ze merken op dat hoewel hun IPM een slechtere afhankelijkheid van $d$ heeft ($d^5$ vs $d$), het een "white-box" benadering vertegenwoordigt die de interne structuur van IPM's exploiteert, terwijl de cutting-plane methode een "black-box" toepassing van Grover-zoekopdrachten is.

Betekenis en Claims

Het artikel claimt een positief antwoord te geven op de vraag of kwantumalgoritmen Interior Point Methods kunnen versnellen voor "hoge" lineaire programma's.

• Sublineaire Versnelling: De primaire betekenis is het bereiken van een sublineaire tijd- en querycomplexiteit in het aantal beperkingen $n$ voor hoge LP's, een regime waarin klassieke algoritmen lineair in $n$ zijn.
• Nieuwe Subroutines: Het werk introduceert nieuwe kwantumsubroutines voor spectrale benadering en Lewis weight berekening die van onafhankelijk belang zijn voor statistische regressie en dimensionaliteitsreductie.
• Onafhankelijkheid van Conditiegetal: In tegenstelling tot eerdere kwantum IPM-voorstellen die vertrouwden op kwantum lineaire systeem solvers (wat conditiegetal-afhankelijkheden introduceerde), vermijdt deze aanpak dergelijke afhankelijkheden door spectrale benadering en preconditioning.
• Foutafhankelijkheid: Het algoritme bereikt een $\log(1/\epsilon)$ afhankelijkheid van de precisie, wat een verbetering is ten opzichte van eerdere kwantum LP-algoritmen die vaak een polynomiale afhankelijkheid van $1/\epsilon$ hadden.

De auteurs blijven bescheiden over de $d$-afhankelijkheid en erkennen dat hun huidige bound ($d^5$) aanzienlijk slechter is dan de $\sqrt{n} d$ bound van de cutting-plane benchmark. Ze identificeren het verbeteren van de gradiëntbenadering en het benutten van dynamische datastructuren als belangrijke openstaande richtingen om deze kloof te dichten.