Генерация «бесконечной» случайности из постоянного числа источников

11

Недавно я наткнулся на статью Кудрона и Юена о расширении случайности с использованием квантовых устройств. Основным результатом работы является то, что можно генерировать «бесконечную» случайность из постоянного числа источников (то есть количество генерируемых случайных битов зависит только от количества циклов протокола, а не от количества источников). ).

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

Но я не очень понимаю квантовую теорию информации и уверен, что мне не хватает многих тонкостей. Не говоря уже о том, что если бы такие претензии были возможны, авторы сделали бы это. Итак, мой вопрос:

Означает ли существование «бесконечного расширения случайности», как описано в статье (и всех связанных с этим работах), своего рода утверждения дерандомизации для рандомизированных классов сложности? И если нет, то почему ?

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

Суреш Венкат
источник
2
Непосредственно не обращаясь к вопросу, но вот еще одно высокоуровневое описание и обсуждение области и результата одного из двух авторов в блоге Теории MIT .
Климент С.
Я думаю, что расширение квантовой случайности направляет ортогональный вопрос к дерандомизации. В частности, предполагается, что у вас уже есть устройства, которые могут генерировать случайные биты. Вопрос, который решается, заключается в проверке случайности этих устройств, что само по себе требует использования рандомизированных тестов. Расширение относится к тому, сколько случайности необходимо для теста по сравнению с тем, сколько новых случайностей создается устройствами во время теста.
Томас

Ответы:

15

Это отличный вопрос, Суреш!

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

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

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

Другими словами, это интерактивное доказательство генерации случайности.

Таким образом, единственный аспект «дерандомизации» состоит в том, чтобы утверждать, что сам протокол требует небольшой случайности запуска. Но результат очень не дерандомизирован: результат, создаваемый блоками, является истинной случайностью, а не псевдослучайностью (то есть без вычислительных предположений).

Генри Юн
источник
1
Понимаю. Таким образом, в то время как в «нормальном» аргументе дерандомизации (скажем, через расширитель) именно «конструктор алгоритмов» создает доказательство правильности. Здесь это фактическое интерактивное доказательство, которое устанавливает доказательство случайности, которое отличается.
Суреш Венкат
Это точно верно!
Генри Юн