Что такое «выборка по случайной схеме»?

12

Многие люди предлагают использовать «выборку по случайной схеме» для демонстрации квантового превосходства. Но каково точное определение проблемы "выборки по случайной схеме"? Я видел утверждения типа «задача состоит в том, чтобы взять случайную (эффективную) квантовую схему определенной формы и сгенерировать выборки из ее выходного распределения». Но мне не ясно, что именно означают термины «случайная (эффективная) квантовая схема». Кроме того, знаем ли мы что-нибудь о классической вычислительной сложности этой проблемы?

Grok
источник
Я не вижу, чтобы Джеймс Вуттон упоминал о сложности проблемы RCS, поэтому она # P-hard, см. Эту статью: arxiv.org/pdf/1803.04402.pdf
YOUSEFY

Ответы:

13

n2n

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

|0

n

nn

nn

Детали того, как именно нужно создать случайную цепь, и что нужно искать в результатах, чтобы объявить успех, зависят от предложения (например, от Google). Также еще не ясно, сколько кубитов необходимо, чтобы современные суперкомпьютеры не смогли воспроизвести результат.

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