Kvant 6, 876 (2022).
https://doi.org/10.22331/q-2022-12-13-876
Många kvantalgoritmer för numerisk linjär algebra antar black-box-åtkomst till en blockkodning av matrisen av intresse, vilket är ett starkt antagande när matrisen inte är gles. Kärnmatriser, som uppstår från diskretisering av en kärnfunktion $k(x,x')$, har en mängd olika tillämpningar inom matematik och teknik. De är i allmänhet täta och fulla. Klassiskt utför den berömda snabba multipolmetoden matrismultiplikation på kärnmatriser med dimensionen $N$ i tid nästan linjär i $N$ genom att använda det linjära algebraiska ramverket för hierarkiska matriser. I ljuset av denna framgång föreslår vi ett blockkodningsschema för den hierarkiska matrisstrukturen på en kvantdator. När den tillämpas på många fysiska kärnmatriser kan vår metod förbättra körtiden för att lösa kvantlinjära system med dimensionen $N$ till $O(kappa operatornamn{polylog}(frac{N}{varepsilon}))$, där $kappa$ och $varepsilon$ är villkorsnumret och felgränsen för matrisoperationen. Denna körtid är nästan optimal och, i termer av $N$, förbättras exponentiellt jämfört med tidigare kvantlinjära systemalgoritmer i fallet med täta och fullrankade kärnmatriser. Vi diskuterar möjliga tillämpningar av vår metodik för att lösa integralekvationer och accelerera beräkningar i N-kroppsproblem.
