Was ist der Zweck eines Quanten-RAM in Quantenalgorithmen?

17

Ich sehe viele Arbeiten (zB Quantum Principal Component Analysis ), in denen die Existenz von qRAM notwendig ist. Was ist der eigentliche Zweck von qRAM in Quantenalgorithmen?

Anton Karazeev
quelle
1
Hallo, wir bevorzugen es, wenn ein Beitrag nur eine Frage enthält. Auch Probleme, mit denen wir konfrontiert werden, werden wahrscheinlich zu Diskussionen / Meinungen führen und sind daher nicht die beste Frage für Quantum Computing StackExchange.
MEE - Wiedereinsetzung von Monica am
@MEE ersetzte zwei Fragen durch eine.
Anton Karazeev

Antworten:

6

Dies wird in Kapitel 5 von Ciliberto et al. .

Der Zweck der meisten quantenbasierten (erweiterten) Algorithmen für maschinelles Lernen besteht darin, die Verarbeitung klassischer Daten zu beschleunigen, was mit klassischen Algorithmen für maschinelles Lernen möglich ist. Mit anderen Worten, der Kontext ist, dass Sie eine Menge klassischer Vektoren haben und eine Funktion f ( x k ) dieser Daten berechnen möchten (die dann als Schätzer für eine Eigenschaft verwendet werden kann, oder als eine Funktion, die einen Klassifikator kennzeichnet, der für neue Datenpunkte oder etwas anderes verwendet werden soll). Die meisten Quanten Algorithmen für maschinelles Lernen Ihnen sagen, dass, sofern Sie in der Lage sind , um effizient das Mapping durchzuführen {{xk}kf(xk) dann ist es manchmal möglich, compute f ( { x k } ) effizienter. Es ist jedoch höchst unwichtig, wie ein solches Mappingeffizient durchgeführt werden kann.

{xk}k|{xk}=Nkjxkj|k,j,
f({xk})

Um die potenziellen exponentiellen Beschleunigungen der Quantenalgorithmen aufrechtzuerhalten, muss diese Umwandlung effizient sein. Ist dies nicht der Fall, kommt es zu einer Situation, in der der Quantenalgorithmus das Problem sehr effizient lösen kann, jedoch erst, nachdem eine langwierige Vorverarbeitung der Daten durchgeführt wurde, was den ganzen Sinn der Verwendung des Quantenalgorithmus zunichte macht.

Hier kommen QRAMs ins Spiel. Ein QRAM ist eine Vorrichtung, die (theoretisch) d -dimensionale klassische Vektoren in (die Amplituden von) einem Quantenzustand von log ( N d ) Qubits in der Zeit O ( log ( N d ) ) codieren kann . Wie in Ciliberto et al. Wie auch in dieser verwandten Antwort ist die tatsächliche Machbarkeit von QRAMs immer noch nicht ganz klar, und viele Vorbehalte bleiben bestehen.N dLog(Nd)Ö(Log(Nd))

glS
quelle