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