Квантовые вычисления со времен Демокрита - Скотт Ааронсон

случае квантовых состояний мы уже не работаем с булевыми функциями. Вы можете рассматривать квантовое состояние как действительную функцию, которая принимает в качестве входного сигнала двухвариантное измерение E и выдает на выходе действительное число из интервала [0, 1] (а именно вероятность того, что измерение принимает). То есть ρ берет измерение E и возвращает Tr(Eρ).

Итак, можно ли обобщить результат Блумера и соавторов на функции с действительными значениями? К счастью, это уже сделали до меня Алон, Бен-Давид, Чеза-Бьянки и Хаусслер, а также, помимо прочих, Бартлетт и Лонг.

Далее, вспомним из главы 14 нижнюю оценку кодов произвольного доступа Амбайниса, Наяка и др., которая говорит нам, сколько классических битов можно надежно зашифровать в состояние из n кубитов. Пусть дана m-битная классическая строка x, и предположим, что мы хотим зашифровать x в квантовое состояние из n кубитов таким способом, что любой бит xi по нашему выбору можно было бы позже извлечь с вероятностью по крайней мере 1 — ε. Амбайнис с соавторами доказали, что на самом деле мы не можем ничего сэкономить, упаковав классические биты в квантовое состояние таким способом. То есть n по-прежнему должно быть линейно относительно m. Поскольку это нижняя оценка, мы можем рассматривать ее как ограничение схем квантового шифрования. Но мы можем также перевернуть все с ног на голову и сказать: это реально хорошо, поскольку подразумевает некую верхнюю оценку VC-размера квантовых состояний, рассматриваемых как класс концепций. Грубо говоря, эта теорема говорит нам, что VC-размер n-кубитных состояний, рассматриваемых как класс концепций, равен максимум m = O(n). Чтобы формализовать ситуацию, нам нужен действительный аналог VC-размера (известный как «сжигатель жира»; не спрашивайте, почему), а также теорема о том, что мы можем усвоить любой действительный класс концепций при помощи числа образцов, возрастающего линейно с ростом жиросжигающего размера.

А что можно сказать о возможности реально найти это состояние? Даже в классическом случае я полностью игнорировал вычислительную сложность нахождения гипотезы. Я сказал, что если вы каким-то образом нашли гипотезу, которая согласуется с имеющимися данными, то все в порядке, вы сможете объяснить будущие данные, — но как вы будете искать эту гипотезу? Мало того, как вы хотя бы запишете ответ в квантовом случае? Явная запись состояния потребовала бы экспоненциально много битов! С другой стороны, может быть, все не так плохо, ведь даже в классическом случае на поиск гипотезы может потребоваться экспоненциальное время.

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

Однако я могу рассказать вам кое-что из того, что известно для классического случая. Может быть, к нашему разочарованию, значительная часть известного имеет отношение к трудности. К примеру, для класса концепций булевых схем полиномиального размера мы считаем вычислительно трудной задачей поиск схемы (или, что эквивалентно, короткой эффективной компьютерной программы), которая выдавала бы на выходе уже виденные нами данные, даже в предположении, что такая схема существует. Разумеется, мы не можем доказать, что эта задача не имеет алгоритма полиномиального времени (ведь тем самым мы доказали бы, что P ≠ NP); мало того, оказывается, мы не можем даже доказать при нынешнем уровне знания, что это NP-полная задача. Мы знаем, что эта задача по крайней мере столь же трудна, как инвертирование односторонних функций, то есть взлом почти всей современной криптографии. Помните, когда мы в главе 8 говорили о криптографии, мы упоминали односторонние функции, которые легко вычислять, но трудно инвертировать? Мы тогда говорили, что Хостад, Импальяццо, Левин и Луби[126] в 1997 г. доказали, что из любой односторонней функции можно построить псевдослучайный генератор, отображающий n «истинно» случайных битов на, скажем, n2 битов, которые не отличит от случайных никакой алгоритм полиномиального времени. А Голдрейх, Гольдвассер и Микали ранее показали[127], что из любого псевдослучайного генератора можно построить семейство псевдослучайных функций — семейство булевых функций f:{0, 1}n → {0, 1}, которые вычисляются небольшими схемами, но которые не отличит от случайных функций никакой алгоритм полиномиального времени. А такое семейство функций немедленно ведет нас к вычислительно неразрешимой задаче обучения.

Итак, на основании криптографических допущений мы можем показать, что задачи поиска гипотезы для объяснения уже виденных данных, вероятно, трудны в общем случае. После небольшой модификации этого результата мы можем сказать, что если поиск квантового состояния, согласующегося со сделанными измерениями, всегда может быть проведен эффективно, то не существует односторонней функции, надежно защищающей от квантовых атак. Это означает, что нам, по существу, придется расстаться с надеждой решить эти задачи обучения в общем и ограничиться конкретными случаями. В классическом случае существуют особые классы концепций, которые можно эффективно изучить, такие как схемы постоянной глубины или функция четности. Я уверен, что в квантовом мире дело обстоит приблизительно так же.

Загадка

В дополнение к уже упоминавшейся задаче распознавания прямоугольника существует еще одна задача про воронов авторства Карла Хемпеля. Пусть мы хотим проверить свою любимую гипотезу о том, что все вороны — черные. Как мы это делаем? Мы выходим в поле, находим там воронов и смотрим, действительно ли они все черные. С другой стороны, возьмем заявление, противоположное нашей гипотезе и логически ей эквивалентное: все нечерные объекты не являются воронами. Это позволяет предположить, что орнитологические исследования можно проводить, не выходя из офиса! Мне достаточно просто смотреть на случайные объекты, отмечать про себя, что они не черные, и проверять, не являются ли они воронами. По мере работы у меня накапливаются данные о том, что все увиденные нечерные объекты — не вороны, что подтверждает мою гипотезу. Загадка в том, работает ли такой подход. Разрешается считать (для этой задачи), что я не выхожу из офиса в поля, леса или куда-то еще, чтобы наблюдать за птицами.

17. Интерактивные доказательства, нижняя оценка сложности схемы и многое другое

В завершение предыдущей главы я дал вам загадку: можно ли быть орнитологом, не выходя из офиса?

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