Квантовые вычисления были рассмотрены Фейнманом как ценное средство решения квантовых задач.
Распространенным заблуждением при описании мощности квантового компьютера по сравнению с классическим компьютером является то, что квантовые биты могут быть получены в виде суперпозиции экспоненциального числа состояний, чего нельзя достичь с помощью классических битов. Это утверждение, безусловно, верно, но оно не говорит, в частности, какие проблемы могут эффективно решить квантовые компьютеры, в то время как классические компьютеры этого не делают.
Фактически, основываясь именно на технике интеграла по путям Фейнмана, выход (то есть амплитуда перехода) любой квантовой цепи может быть рассчитан классически с полиномиальным объемом памяти (хотя временные затраты будут экспоненциальными). Поэтому любое квантовое вычисление можно моделировать классически.
Было предпринято много усилий, чтобы определить мощь квантовых компьютеров на основе механизма теории вычислительной сложности. В частности, класс вычислительных задач, которые могут быть эффективно решены квантовым компьютером, называется BQP (квантовое полиномиальное время с ограниченной ошибкой); аналог для классических компьютеров называется P (полиномиальное время). Конечно, BQP не может быть меньше P; в принципе, квантовые компьютеры могут эффективно моделировать классические компьютеры. Дело в том, что основы квантовых вычислений не могут быть установлены без доказательства, показывающего, что BQP строго больше, чем P (то есть BQP ≠ P). В этом смысле этот вопрос столь же интересен, как и знаменитая задача доказательства P ≠ NP (недетерминированного полиномиального времени).
Хорошо известным примером проблемы NP является проблема факторинга. Однако, до сих пор нельзя строго исключить возможность существования эффективного классического алгоритма факторинга. Хотя опять-таки без доказательств, обычно считают, что квантовые компьютеры не могут решить некоторые проблемы NP. Фактически, доказательство этого утверждения (если оно истинно) обеспечивает возможный путь доказательства P ≠ NP.
Потенциально менее требовательный вопрос будет, когда мы ожидаем, что квантовый компьютер сможет выполнять некоторые четко определенные задачи (не обязательно связанные с какой-либо практической проблемой), которые не могут быть смоделированы с помощью любого доступного в настоящее время классического устройства, в течение разумного времени. Достигнутый статус называется «квантовым превосходством». Проблема заключается в том, что вместо того, чтобы принять предел больших N, квантовое превосходство требует определения фактического числа кубитов и вентилей, которые больше не могут моделироваться классическими компьютерами в течение разумного времени.
Может быть два понятия классического моделирования, а именно «сильное моделирование» против «слабого моделирования».
Сильное моделирование относится к случаям вычисления вероятностей переходов или ожидаемых значений, наблюдаемых с высокой точностью за полиномиальное время.
Слабое моделирование требует точного воспроизведения распределений вероятностей, что предполагает «выборку» различных результатов квантовых устройств. Некоторые квантовые схемы, которые не могут быть строго смоделированы с помощью эффективных классических средств, могут иметь эффективные классические методы для слабого моделирования.
Тем не менее, нужно быть осторожным с требованием точности в задачах моделирования. Например, для многих задач может быть достаточно определить амплитуды перехода с точностью до аддитивной ошибки вместо мультипликативной ошибки. Другими словами, классическая симуляция квантовых вычислительных задач зависит от требования к точности.
В настоящее время существует три популярных подхода для достижения квантового превосходства, а именно:
- выборка бозонов;
- выборка IQP (мгновенных квантовых полиномов) цепей;
- выборка хаотических квантов схемы.
Во всех этих подходах распределения различных цепочек битов или числа фотонов выбираются из квантовых устройств. Кроме того, все они предполагают, что классические компьютеры не способны эффективно определять амплитуды перехода и / или воспроизводить (или приближать) распределения квантовых устройств, выполняющих эти задачи, в смысле как сильного, так и слабого моделирования.
При бозонной выборке одиночные фотоны вводятся в различные моды линейной оптической сети. Задача состоит в том, чтобы определить распределение фотонов на выходных портах. Ключевой особенностью дискретизации бозонов является то, что амплитуды переходов связаны с перманентами комплексных матриц, которые, как правило, очень трудно рассчитать точно или приблизительно с точностью до мультипликативной ошибки. Более того, считается, что эффективное слабое моделирование выборки бозонов невозможно, если только полиномиальная иерархия не рухнет на свой третий уровень. Но для достижения квантового превосходства с помощью отбора проб бозонов необходимо одновременно генерировать по меньшей мере 50 или более одиночных фотонов, что по-прежнему является технологически сложной задачей.
Вопрос заключается в том, может ли линейная оптика при настройке бозонной выборки применяться для решения задач. В этом случае может потребоваться определить амплитуды перехода с учетом аддитивной ошибки. Тем не менее, большой класс проблем, связанных с отбором проб бозонов, может быть смоделирован на классическом компьютере.
Хаотические квантовые схемы относятся к классу квантовых схем, где двухбитные вентили применяются регулярно, в то время как однобитные вентили применяются случайным образом из набора вентилей. Выходные распределения этих схем приближаются к так называемому распределению Портера – Томаса, которое является характерной чертой квантового хаоса. В последнее время было проведено несколько исследований, направленных на изучение предела классических вычислений при моделировании квантовых цепей малой глубины. Для идеальных случаев необходимо учитывать, как число кубитов, так и глубину цепи для сравнительного анализа квантового превосходства. Однако в присутствии шума эти хаотические схемы могут также стать классически симулируемыми для схем с большой глубиной.
Наконец, помимо этих трех подходов следует ожидать, что квантовое превосходство может быть достигнуто для многих практических приложений, например, для моделирования квантовой химии или обучения квантовой машине. Время покажет, когда это произойдет!
Если вам было интересно – ставьте лайк и подписывайтесь на мой канал!