Какие протоколы были предложены для реализации квантовых RAM?

16

Решающая роль памяти с произвольным доступом (RAM) в контексте классических вычислений заставляет задуматься, как можно обобщить такую ​​концепцию в квантовой области.

Возможно, самой заметной (и первой?) Работой, предлагающей эффективную архитектуру QRAM, является Giovannetti et al. 2007 . В этой работе было показано, что их подход «ведущий бригат» позволяет получить доступ к содержимому памяти с помощью операций , где N - количество слотов памяти. Это экспоненциальное улучшение по сравнению с альтернативными подходами, которые требуют операций O ( N α ) . Однако реализация этой архитектуры весьма нетривиальна с экспериментальной точки зрения.O(logN)NO(Nα)

Вышеуказанный единственный известный способ реализации QRAM? Или были другие теоретические работы в этом направлении? Если да, то как они сравниваются (плюсы и минусы) с Giovannetti et al. предложение?

GLS
источник

Ответы:

7

Резюме хорошо о текущем состоянии КОРА (по состоянию на 2017 г.) можно найти в этой статье , и сравнение его с классическими методами можно найти в этом разговоре . QRAM типа «Ковш-бригада» Джованнетти по- прежнему кажется лучшим из известных, хотя модификации существуют. Существуют серьезные предостережения относительно использования любой такой QRAM, и пока не было предложено никакой альтернативы, которая бы избегала их (кроме использования классически распараллеленных компьютеров).

N dжурнал(Nd)О(журнал(Nd))

Проблема зависит от того, сколько компонентов должно быть активным одновременно. В идеале, количество активных компонентов должно быть только линейным с количеством кубитов в памяти. Однако фактические реализации обычно далеки от идеальных.

В этой статье , например, рассматривается влияние шума и делается вывод о том, что необходимость исправления ошибок может устранить любые преимущества небольшого количества активных компонентов. Серьезность этой потенциальной проблемы зависит от того, какой алгоритм используется квантовым компьютером, и сколько раз необходимо запросить QRAM. Для полиномиального количества запросов можно было бы избежать полной отказоустойчивости. Но для суперполиномиальных запросов, таких как поиск Гровера, полная терпимость кажется необходимой.

Что касается сравнения с другими возможностями, то утверждается, что экспоненциальное количество ресурсов для QRAM следует сравнивать с классической параллельной архитектурой с экспоненциальным числом процессоров. Квантовый алгоритм не выглядит так здорово с этим сравнением. Как объясняется здесь , некоторые алгоритмы, для которых мы ожидаем квантовое ускорение, на самом деле медленнее, если учитывать этот параллелизм.

Хотя не столь общий характер, еще одно предложение для сдачи классических данных в суперпозицию также было предложено здесь и так заслуживает упоминания.

Джеймс Вуттон
источник