Загадка из предыдущей главы известна как проблема индукции Юма.

Загадка. Если вы наблюдаете 500 черных воронов, то какие у вас основания ожидать, что следующий ворон, которого вы увидите, тоже будет черным?

Многие люди в ответ апеллируют к теореме Байеса. Однако, чтобы такое обращение сработало, нужно сделать некоторые допущения; к примеру, считать, что все вороны берутся из одного и того же распределения. И если мы откажемся считать, что будущее похоже на прошлое, то очень трудно будет сделать хоть что-нибудь. Такого рода вопросы породили множество философских споров, к примеру таких.

Предположим, вы видите кучку изумрудов, и все они зеленые. Казалось бы, это придает достоверности гипотезе о том, что все изумруды зеленые. С другой стороны, мы можем придумать слово зелебой и определить его так: «зеленый до 2050 г., а после этого голубой». Тогда камни, которые вы видите перед глазами, столь же уверенно подтверждают гипотезу о том, что все изумруды зелебые, а не зеленые. Эта ситуация известна как парадокс зелебого.

Если вы хотите нырнуть в эту тему еще «глубже», давайте рассмотрим парадокс гавагаи. Предположим, что вы пытаетесь изучить язык и что вы — антрополог, посетивший амазонское племя, которое говорит на этом языке. (Или, может быть, вы младенец этого племени. Так или иначе, представьте, что вы пытаетесь освоить язык племени в процессе общения.) Далее, предположим, мимо пробегает антилопа, и кто-то из членов племени указывает на нее и кричит: «Гавагаи!» Кажется разумным заключить из этого, что слово «гавагаи» на их языке значит «антилопа», но откуда вам знать, что оно не указывает всего лишь на рог антилопы? Или, может быть, это название конкретной разновидности антилоп, представитель которой и пробегал мимо. Хуже того, это может означать, что некая конкретная антилопа пробежала мимо в конкретный день недели! Возможно огромное число ситуаций, на которые мог ссылаться представитель племени, используя это слово, поэтому мы должны сделать вывод о том, что выучить язык невозможно, сколько бы времени мы ни провели в племени.

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

«Ну, никогда раньше это не срабатывало…»

Мы здесь хотим поговорить об эффективности обучения. Мы уже видели все те философские проблемы, которые указывают, на первый взгляд, что обучение невозможно, но мы знаем также, что обучение имеет место в реальности; поэтому мы хотим дать какое-то объяснение тому, как оно происходит. В философии это своего рода проблема, но мне кажется, что вся обстановка вокруг нее в последние годы претерпела очень серьезные изменения благодаря так называемой теории вычислительного обучения. Эта теория известна не так широко, как того заслуживает. Даже если вы (скажем) физик, вам полезно знать кое-что об этой теории, поскольку она задает отправную точку — не ту, что дает более известная байесовская позиция, но связанную с ней и, возможно, более полезную в некоторых ситуациях — для решения вопроса о том, можно ли ожидать от той или иной теории предсказания будущих результатов.

Мне кажется, ключевой момент, который должен приниматься во внимание при любом подходе, будь то байесизм, теория вычислительного обучения или еще что-то, состоит в том, что мы никогда не рассматриваем все логически представимые гипотезы на равных основаниях. Если у вас имеется 500 воронов, каждый из которых либо бел, либо черен, то в принципе существует 2⁵⁰⁰ гипотез, которые вам следует рассмотреть. Если вороны могут быть не только черными и белыми, но и зелеными, гипотез будет еще больше. Однако в реальности мы никогда не рассматриваем все эти гипотезы как равно возможные. Мы всегда ограничиваем свое внимание некоторым небольшим подмножеством гипотез — их можно назвать «достаточно простыми» гипотезами, — если только данные не вынуждают обратиться к более сложным гипотезам. Иными словами, мы всегда неявно используем так называемую «бритву Оккама» (хотя совершенно неясно, это ли имел в виду сам Оккам).

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

Но это все пустые разговоры. Можем ли мы на самом деле понять, как взаимосвязаны число рассматриваемых гипотез и степень уверенности, с которой мы предсказываем будущее? Один из способов сделать это сформулировал Лесли Валиант в 1984 г.[123] Его подход называется PAC-обучение, где PAC означает «probably approximately correct» («вероятно почти корректное»). Мы не собираемся предсказывать все, что происходит в будущем, не собираемся даже предсказывать с определенностью большую часть, но с высокой вероятностью мы попытаемся предсказать большую часть верно.

Возможно, это звучит как чистая философия, но часть этих рассуждений можно напрямую связать с экспериментами. К примеру, эту теорию использовали в экспериментах с такими вещами, как нейронные сети и машинное обучение. Когда-то в процессе написания статьи о PAC-обучении я захотел выяснить, как эта теория реально используется, и заглянул на «Академию Google». На момент публикации этой книги статья Валианта была процитирована 4000 раз. На основании этого можно заключить, что следует ожидать дальнейших публикаций на эту тему.

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

Концепция — это булева функция f: S → {0, 1}, отображающая каждый элемент пространства примеров либо на 0, либо на 1. Позже мы можем отбросить допущение о том, что концепции представляют собой булевы функции, но для простоты мы пока будем считать их таковыми. В нашем примере концепция — это язык, который мы пытаемся изучить; получив предложение, концепция сообщает нам, верно ли оно грамматически. Далее, мы можем получить класс концепций и обозначить его C. Здесь C можно считать множеством языков, которые наш младенец, приходя в мир, считает в принципе возможными еще до получения каких-либо данных о реальном используемом языке.

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

Какова же цель всего этого? Мы получаем m образцов xi, извлеченных независимо из распределения D, и для каждого x_i мы получаем f(x_i), то есть нам сообщают, верен ли грамматически каждый из наших образцов. Пользуясь этими данными, мы хотим создать язык-гипотезу h, такой, что

где ~ означает, что x берется из распределения D. То есть мы хотим, чтобы наша гипотеза h расходилась с концепцией f не более чем в доле ε примеров x, извлеченных из распределения D. Можем ли мы уверенно надеяться на такой результат? Нет? Ну почему же нет?

Вам может не повезти с получаемыми образцами; так, можно извлекать из распределения один и тот же образец снова и снова. Если единственное предложение, которое вам доведется слышать младенцем, будет: «Какой умный малыш!», то у вас не выработается никакой базы, на основании которой вы сможете определить, является ли также предложением фраза: «Мы считаем эти истины самоочевидными». В общем-то, следует считать, что возможных предложений существует экспоненциально много, но младенец слышит из них лишь полиномиальное количество.

Итак, мы говорим, что должны лишь выдать только ε-хорошую гипотезу с вероятностью 1 — δ по выбору примеров. Теперь можно привести основную теорему из статьи Валианта.

Теорема. Чтобы удовлетворить требованию о том, что результирующая гипотеза h согласуется с 1 — ε будущих данных из тех, что будут случайно отобраны из D, с вероятностью 1 — δ по выбору примеров, достаточно найти такую произвольную гипотезу h, которая согласуется с

образцами, отобранными независимым образом из D.

Ключевой момент в отношении этой оценки заключается в том, что она логарифмически связана с числом возможных гипотез |C|. Даже если гипотез экспоненциально много, эта оценка все равно полиномиальна. Но почему мы требуем, чтобы распределение D, на котором будет тестироваться обучающий алгоритм, совпадало с распределением, из которого извлекаются пробные примеры?

Потому что если ваше пространство образцов представляет собой ограниченное подмножество пространства примеров, то вас обманули.

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

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

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

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

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

Доказывается теорема Валианта совсем несложно. Назовем заданную гипотезу h плохой, если они расходится с f более чем на доле ε данных. Тогда для любой конкретной плохой гипотезы h, поскольку x1, …, xm независимы, мы имеем

Pr[h(x₁) =f(x₁), …,h(x_m) =f(x_m)] < (1 — ε)^m.

Это ограничивает вероятность того, что данная плохая гипотеза дала верные предсказания по образцам. Тогда чему равна вероятность того, что существует плохая гипотеза h ∈ C, которая согласуется со всеми данными выборки? Мы можем воспользоваться границей объединения:

Pr[существует плохая h, которая согласуется с f для всех образцов] < |C| (1 — ε)^m.

Мы можем приравнять эту вероятность к δ и решить уравнение относительно m. Получаем:

Что и требовалось доказать.

Это дает нам границу числа образцов, необходимых для конечного множества гипотез, но как насчет бесконечных классов концепций? К примеру, что если мы пытаемся узнать прямоугольник на плоскости? Тогда наше пространство примеров — это множество всех заполненных прямоугольников. Предположим, нам даны m точек, и для каждой указано, принадлежит она или нет «секретному прямоугольнику».

Итак, сколько у нас возможных прямоугольников? Существует 2^ℵ₀ возможных вариантов, так что мы не можем применить предыдущую теорему! Тем не менее если даны 20–30 случайных точек в прямоугольнике и 20–30 случайных точек вне прямоугольника, но рядом с ним, интуитивно кажется, что мы имеем довольно здравое представление о том, где именно находится прямоугольник. Можем ли мы предложить более общую теорему об обучении, применимую, когда класс концепций бесконечен? Да, но для начала нам понадобится концепция под названием дробление.

Для некоторого класса концепций C мы говорим, что подмножество пространства примеров {s₁, s₂, …, s_k} раздроблено C, если для всех 2^k возможных классификаций s₁, s₂, …, s_k существует некоторая функция f ∈ C, которая согласуется с этой классификацией. Тогда определим VC-размер класса C, обозначаемый VCdim (C), как размер наибольшего подмножества, раздробленного C.

Что представляет собой VC-размер класса концепций прямоугольников? Нам нужно наибольшее множество точек, таких, что для любого возможного распределения их на те, которые принадлежат прямоугольнику и которые не принадлежат, существует некоторый прямоугольник, который содержит только те точки, которые нам нужны, причем все. Нижеследующая диаграмма иллюстрирует, как добиться этого с четырьмя точками. С другой стороны, не существует способа сделать это с пятью точками (доказательство этого пусть будет упражнением для вас!).

Одно из следствий следующей теоремы гласит, что PAC-обучение возможно с конечным числом образцов в том и только том случае, если VC-размер класса концепций конечен.

Теорема (Блумер, Эренфойхт, Хаусслер и Вармут, 1989)[124]. Чтобы получить гипотезу h, способную объяснить долю 1 — ε будущих данных, извлеченных из распределения D, с вероятностью 1 — δ, достаточно построить любую h из C, которая согласуется с

образцов, извлеченных независимо из D. Более того, это точная оценка (с учетом зависимости от ε).

Эту теорему доказать труднее, чем предыдущую, на это потребовалась бы отдельная глава, так что мы опустим доказательство. Интуитивно, однако, за доказательством стоит просто бритва Оккама. Если VC-размер конечен, то после рассмотрения количества образцов, превышающего VC-размер, энтропия уже рассмотренных данных достигнет лишь приблизительно VC-размера. Вы делаете m наблюдений, после чего возможное количество вещей, которые вы уже видели, будет меньше 2^m; в противном случае было бы VCdim (C) ≥ m. Следовательно, для описания этих m наблюдений требуется меньше чем m бит. Это означает, что можно предложить теорию, которая объясняет прошлые данные и содержит при этом меньше параметров, чем сами данные.

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

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

Но что, если вещь, которую мы пытаемся узнать, — это квантовое состояние, скажем некоторое смешанное состояние ρ? Мы могли бы провести измерение E с двояким результатом. В квантовой механике самый общий тип измерения называется положительной операторной мерой (POVM, positive operator valued measure). POVM — это всего лишь обычное «проективное» измерение — измерение того типа, который мы обсуждали ранее, за исключением того, что перед измерением как таковым вы должны провести произвольное унитарное преобразование измеряемого состояния ρ вместе с некоторым дополнительным «вспомогательным состоянием», не зависящим от ρ. В данном случае вам достаточно знать следующее: если у вас имеется POVM M с двумя возможными исходами, действующее на n-мерном смешанном состоянии ρ, то вы можете полностью характеризовать M при помощи эрмитовой матрицы E размера n × n, все собственные величины которой принадлежат [0, 1]. Тогда вероятность того, что M «принимает» ρ, просто равна tr(Eρ) (где tr, или ранг, есть сумма диагональных элементов), а вероятность того, что M «отвергает» ρ, равна 1 — tr(Eρ).

Далее, если нам дано некоторое состояние ρ, то мы бы хотели иметь возможность предсказывать результат любого измерения, проведенного над этим состоянием, то есть оценивать вероятность принятия tr(Eρ) для любого двухвариантного POVM-измерения E. Легко убедиться, что это эквивалент томографии квантового состояния, то есть выяснения самой матрицы плотности ρ.

Но что такое ρ? Это некоторое n-кубитное состояние, представленное в виде матрицы 2ⁿ × 2ⁿ с 4ⁿ независимых параметров. Хорошо известно, что число измерений, необходимых для томографии n-кубитного состояния, растет экспоненциально с n. Уже одно это представляет серьезную практическую проблему для экспериментаторов. Чтобы узнать восьмикубитное состояние, вам, может быть, придется настроить свой детектор 65536 разными способами и провести с каждой настройкой не одну сотню измерений, чтобы добиться приемлемой точности.

Повторюсь, это практическая проблема для экспериментаторов. Но не является ли это также и концептуальной проблемой? Некоторые скептики в отношении квантовых вычислений, судя по всему, считают именно так; в предыдущей главе мы видели, что одно из фундаментальных возражений против квантовых вычислений состоит в том, что в них требуется манипулировать именно такими экспоненциально длинными векторами. Для некоторых скептиков это изначально абсурдный способ описания физического мира, и либо квантовая механика не выдержит, когда мы попытаемся проделать что-то подобное, либо найдется что-нибудь еще, что мы пока не приняли во внимание, потому что очевидно неприемлемо иметь 2n «независимых параметров» в описании n частиц.

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

В 2006 г. я опубликовал статью[125], в которой попытался использовать для ответа на этот аргумент теорию вычислительного обучения. Вот как Умеш Вазирани объяснил мой результат. Он сказал: предположим, вы младенец, который пытается усвоить некое правило, позволяющее предсказывать, является ли заданный объект стулом. Вы видите кучу предметов с ярлыками «стул» или «не стул» и на основании этого вырабатываете собственные общие правила («у стула четыре ножки», «на стуле можно сидеть» и т. п.), отлично работающие в большинстве случаев. Правда, эти правила могут отказать, если (скажем) вы находитесь в музее современного искусства, но мы не будем об этом беспокоиться. В теории вычислительного обучения мы хотим предсказывать не все, а лишь большую часть будущих наблюдений. Если вы простой обыватель и не ходите в музей современного искусства, то вам нечего беспокоиться о стулоподобных объектах, которые можно там обнаружить. Нам следует принимать во внимание будущие намерения обучающегося, поэтому мы смягчаем цель томографии квантового состояния и говорим, что она заключается в предсказании исхода большинства измерений, взятых из некоторого распределения вероятностей D.

Более формально, если задано смешанное состояние ρ на n кубитах, а также измерения E₁, E₂, …, E_m ~ D и расчетные вероятности p_j ≈ Tr(E_jρ) для каждого j ∈ {1, 2, …, m}, то цель состоит в том, чтобы сформировать гипотетическое состояние σ, которое с вероятностью не менее 1 — δ имеет свойство

Для этой цели существует теорема, ограничивающая число необходимых образцовых измерений.

Теорема. Зафиксируем параметры ошибки ε, δ и γ и зафиксируем также η > 0, такое, что γε ≥ 7η. Назовем E = (E₁, …, E_m) «хорошим» обучающим множеством измерений, если любое гипотетическое состояние σ, удовлетворяющее условию |Tr(E_iσ) — Tr(E_iρ) | ≤ η, удовлетворяет также

В этом случае существует константа K > 0, такая, что E будет хорошим обучающим множеством с вероятностью по крайней мере 1 — δ над E₁, …, E_m, извлеченными из D, при условии что m удовлетворяет условию

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

Почему эта теорема верна? Вспомните результат Блумера и др., который гласит, что можно обучаться с числом образцов, растущим линейно вместе с VC-размером вашего класса концепций. В случае квантовых состояний мы уже не работаем с булевыми функциями. Вы можете рассматривать квантовое состояние как действительную функцию, которая принимает в качестве входного сигнала двухвариантное измерение 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}ⁿ → {0, 1}, которые вычисляются небольшими схемами, но которые не отличит от случайных функций никакой алгоритм полиномиального времени. А такое семейство функций немедленно ведет нас к вычислительно неразрешимой задаче обучения.

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