I detta papper konstruerar vi kvantalgoritmer för matrisprodukter över flera algebraiska strukturer som kallas semirings, inklusive produkten (max, min)-matris, distansmatrisprodukten och den booleska matrisprodukten. I synnerhet får vi följande resultat. • Vi konstruerar en kvantalgoritm beräkning produkten av två n × n matriser över (max, min) semiring med tids komplexitet O (n 2.473 ). Som jämförelse, den mest kända klassiska algoritmen för samma problem, av Duan och Pettie (SODA'09), har komplexitet O(n 2.687 ). Som en applikation får vi en O(n 2.473 )-tid kvantalgoritm för beräkning av alla-par flaskhals vägar i en graf med n hörn, medan klassiskt den bästa övre gränsen för denna uppgift är O(n 2.687 ), återigen av Duan och Pettie. • Vi konstruerar en kvantalgoritm beräkning av l mest betydande bitar av varje ingång av distansprodukten av två n × n matriser i tid O(20.64l n 2.46 ). I jämförelse, före detta arbete, den mest kända klassiska algoritmen för samma problem, av Vassilevska och Williams (STOC'06) och Yuster (SODA'09), hade komplexitet O(2 l n 2.69 ). Våra tekniker leder till ytterligare förbättringar för klassiska algoritmer samt, minska den klassiska komplexiteten till O(2 0.96l n 2.69 ), vilket ger en sublinjär beroende på 2 l. Ovanstående två algoritmer är de första kvantalgoritmer som presterar bättre än Õ(n 5/2 )-tid okomplicerad kvantalgoritm baserad på kvantsökning efter matrismultiplikation över dessa halvringar. Vi betraktar också den Booleska semiringen och konstruerar en kvantalgoritm som beräknar produkten av två n × n Booleska matriser som överträffar de mest kända klassiska algoritmerna för glesa matriser. Till exempel, om indatamatriser har O(n 1.686... ) icke-noll poster, då vår algoritm har tids komplexitet O(n 2.277 ), medan den bästa klassiska algoritmen har komplexitet Õ(n  ska ), där  och är exponenten för matris multiplikation över ett fält (den mest kända övre gräns på  och är  på  och < 2.373).
Le Gall och Nishimura REF utformade den första kvantalgoritmen för beräkning av Min-Max-produkt i tid O(n 2.473 ), och noterade att varje problem som motsvarar APBP medger en icke-trivial O (n 2.5-ε )-tidsalgoritm i kvantvärlden.
Quantum Algorithms for Matrix Products over Semirings
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Physics', 'Computer Science']}