Quantenmatrix-Multiplikation?

Es scheint nicht so, als ob dies bekannt wäre - aber gibt es interessante Untergrenzen für die Komplexität der Matrixmultiplikation im Quantencomputermodell? Haben wir eine Vorstellung davon, wie wir die Komplexität des Coppersmith-Winograd-Algorithmus mit Quantencomputern überwinden können?

reference-request quantum-computing matrix-product Henry Yuen
quelle

Antworten:

In arXiv: quant-ph / 0409035v2 präsentieren Buhrman und Spalek einen Quantenalgorithmus, der den Coppersmith-Winograd-Algorithmus in Fällen übertrifft, in denen die Ausgabematrix nur wenige Einträge ungleich Null enthält.

Update: Es gibt auch einen leicht verbesserten Quantenalgorithmus von Dörn und Thierauf .

Update: Es gibt einen verbesserten Quantenalgorithmus, bei dem Le Gall Burhman und Spalek im Allgemeinen besiegt.

Martin Schwarz
quelle

Das war neu für mich (ich weiß wenig über Quantenergebnisse), aber als ich auf die Zeitung blickte, war das Ergebnis noch überraschender! Wenn für

Matrixmultiplikationen gibt es

A_{n x m} B_{m x n} = C_{n x n}

$A_{nxm}B_{mxn}=C_{nxn}$

Nicht-Null-Einträge in der Ausgabe, das Produkt kann insubquadratischerZeitberechnetwerden,

o (\sqrt{n})

$o(\sqrt{n})$

o (n m)

$o(nm)$

Daniel Apon

Es gibt eine leichte Verbesserung diesen für den speziellen Fall von Booleschen Matrizenprodukt, min {

} , wenn es

nonzeroes in der Ausgabe. (Es erschien in unserer FOCS'10-Veröffentlichung "Subkubische Äquivalenzen zwischen Pfad-, Matrix- und Dreiecksproblemen".)

n^{1.3} w^{17 / 30}, n^{2} + w^{47 / 60} n^{13 / 15}

$n^{1.3}w^{17/30}, n^2 + w^{47/60} n^{13/15}$

w

$w$

virgi

Eine kürzliche Verbesserung

im Falle der Booleschen Matrixprodukt ist arxiv.org/abs/1112.5855 , mit auch untere Grenzen übereinstimmen.

n w^{1 / 2}

$nw^{1/2}$

Abel Molina

Wenn Sie zwei Matrizen multiplizieren und das vollständige klassische Ergebnis erhalten möchten, ist Martins Antwort wahrscheinlich eine endgültige Antwort auf Ihre Frage. Wenn Sie jedoch etwas wie berechnen möchten, können Sie dies äußerst effizient durchführen. Harrow, Hassidim und Lloyd haben einen Algorithmus ( arXiv: 0811.3171 ) zur Berechnung von der nur in den Dimensionen der Matrix für dünne Matrizen logarithmisch ist . Es scheint relativ einfach, diesen Ansatz anzupassen, um Produkte zu berechnen, anstatt Umkehrungen. $v^\dagger X Y v$ $v X^{-1} v$ $X$

Joe Fitzsimons
quelle

In diesem Fall hängt die Laufzeit weiterhin von der Bedingungsnummer der Matrizen ab, und die Matrizen müssen komplexe Einträge aufweisen. Wenn X und Y spärlich sind, ist auch ihr Produkt spärlich, und

kann klassisch mit der gleichen Art der exponentiellen Beschleunigung unter Verwendung von Zufallsstichproben geschätzt werden.

v^{'} X Y v

$v'XYv$

Aram Harrow

@Aram: Guter Punkt! Ich weiß, dass Ihr Algorithmus für dünne Matrizen funktioniert, aber ich hatte den Eindruck, dass er auch für bestimmte nicht dünne Matrizen funktioniert. Ist das richtig?

Joe Fitzsimons

Ja, es funktioniert für nicht-spärliche Matrizen, wenn wir gute Möglichkeiten zur Simulation dieser Hamiltonianer kennen. Vielleicht ist hier etwas Nicht-Triviales möglich.

Aram Harrow

@Aram: Erhalten wir mit der von Ihnen verwendeten Codierung nicht auch die Fouriertransformation aller spärlichen Matrizen über die QFT?

Joe Fitzsimons

@ Joe: Ich habe das gerade bemerkt. Ja, diese Matrizen (von denen Sie annehmen können, dass sie auf der Impulsbasis dünn sind) sind ebenfalls verwendbar. Dies ist nichts Einzigartiges an unserem Algorithmus. Es ist eher eine Aussage über die Klasse der Hamiltonianer, die wir auf einem Quantencomputer simulieren können.

Aram Harrow