Jakie protokoły zostały zaproponowane w celu wdrożenia kwantowych pamięci RAM?

16

Kluczowa rola pamięci RAM o dostępie swobodnym w kontekście klasycznych obliczeń sprawia, że ​​naturalne jest zastanawianie się, jak można uogólnić taką koncepcję na dziedzinę kwantową.

Prawdopodobnie najbardziej znaczącą (i pierwszą?) Pracą proponującą wydajną architekturę QRAM jest Giovannetti i in. 2007 . W tej pracy wykazano, że ich podejście „brigowania łyżki” umożliwia dostęp do zawartości pamięci za pomocą operacji , gdzie jest liczbą gniazd pamięci. Jest to wykładnicza poprawa w stosunku do alternatywnych podejść, które wymagają operacji . Wdrożenie tej architektury jest jednak wysoce nietrywialne z eksperymentalnego punktu widzenia.O(logN.)N.O(N.α)

Czy powyższy jedyny znany sposób implementacji pamięci QRAM? A może były inne prace teoretyczne w tym kierunku? Jeśli tak, to w jaki sposób porównują (plusy i minusy) z Giovannetti i in. wniosek?

glS
źródło

Odpowiedzi:

7

Dobre streszczenie obecnego stanu QRAM (od 2017 r.) Można znaleźć w tym artykule , a porównanie tego z metodami klasycznymi można znaleźć w tym wykładzie . Typ Giovannetti „wiadro brygada” QRAM nadal wydaje się być najlepszym, że jest znana, chociaż istnieją modyfikacje. Istnieją poważne zastrzeżenia dotyczące korzystania z takiej pamięci QRAM i nie zaproponowano jeszcze alternatywy, która pozwoli na ich uniknięcie (oprócz użycia masowo zrównoleglonych klasycznych komputerów).

N. relog(N.re)O(log(N.re))

Problem zależy od tego, ile składników musi być jednocześnie aktywnych. W idealnym przypadku liczba aktywnych składników musi być liniowa z liczbą kubitów w pamięci. Jednak rzeczywiste wdrożenia są zwykle dalekie od ideału.

W tym artykule na przykład analizuje się skutki hałasu i stwierdza, że ​​potrzeba korekcji błędów może usunąć wszelkie zalety niewielkiej liczby aktywnych składników. Nasilenie tego potencjalnego problemu zależy od tego, jaki algorytm jest używany przez komputer kwantowy, a więc od tego, ile razy QRAM musi być zapytany. W przypadku wielomianowej liczby zapytań można uniknąć pełnej odporności na uszkodzenia. Ale w przypadku zapytań wielobiegunowych, takich jak wyszukiwanie Grovera, wydaje się potrzebna pełna tolerancja.

Jeśli chodzi o porównanie z innymi możliwościami, argumentowano, że wykładnicza liczba zasobów dla QRAM powinna być porównywana z klasyczną równoległą architekturą z wykładniczą liczbą procesorów. Algorytm kwantowy nie wygląda tak świetnie z tym porównaniem. Jak wyjaśniono tutaj , niektóre algorytmy, dla których spodziewamy się przyspieszenia kwantowego, są faktycznie wolniejsze, jeśli wziąć pod uwagę tę równoległość.

Chociaż nie jest to tak ogólny zakres, zaproponowano tu także inną propozycję umieszczenia klasycznych danych w superpozycjach, dlatego zasługuje na wzmiankę.

James Wootton
źródło