Понятие монотонных квантовых цепей

27

В вычислительной сложности есть важное различие между монотонными и общими вычислениями, и знаменитая теорема Разборова утверждает, что 3-SAT и даже MATCHING не являются полиномами в модели монотонных булевых схем.

Мой вопрос прост: есть ли квантовый аналог для монотонных цепей (или нескольких)? Есть ли квантовая теорема Разборова?

Гил Калай
источник
10
Вот мои два цента: переход от классических схем к квантовым схемам можно разбить на два этапа, добавив классические обратимые схемы в середине. Классические обратимые схемы - это те, в которых разрешены только обратимые ворота. Например, ворота Тоффоли - это универсальные ворота для обратимых вычислений. Я не знаю, как определить понятие монотонности для этих цепей. Мне кажется, что определение монотонных классических обратимых цепей является предпосылкой для определения монотонных квантовых цепей.
Робин Котари
6
(1) (Классическая) обратимая схема реализует биекцию на {0,1} ^ n, и, очевидно, единственная монотонная биекция - это тождественное отображение. Поэтому я не думаю, что разумно определять «монотонные обратимые схемы» нетривиальным образом.
Цуёси Ито
3
(2) Я не уверен насчет квантового случая. Если мы можем определить «монотонные квантовые каналы», то будет естественно определить «монотонные квантовые схемы» как квантовые схемы, набор вентилей которых выбран из монотонных квантовых каналов, так же, как монотонные классические схемы являются схемами, набор вентилей которых выбран из монотонных функций. ,
Tsuyoshi Ito
2
@RobinKothari, TsuyoshiIto: Важность обратимости для квантовых вычислений проистекает именно из частного случая эволюции Шредингера замкнутой системы. Однако, когда мы говорим о логических элементах И и ИЛИ, мы рассматриваем абстрактную физическую систему, которая представляет собой карикатуру на логические элементы, которые находятся в компьютерах; и эти ворота работают именно потому, что они не являются закрытыми системами. Если мы позволим себе говорить о логических элементах AND и OR как таковых, я думаю, что вполне разумно отменить соглашение о рассмотрении замкнутых систем и для квантового вычислительного вопроса.
Ниль де Бёдрап,
3
@Niel, Tsuyoshi: Я думаю, я думал, что монотонная квантовая цепь все еще будет квантовой цепью в традиционном смысле (то есть, унитарные, за которыми следует измерение). Но, следуя аргументу Нила, я думаю, что имеет смысл отбросить это ограничение. Так что мой предыдущий комментарий на самом деле не применим тогда.
Робин Котари

Ответы:

17

Вы действительно задаете два разных вопроса и надеетесь, что существует один ответ, который отвечает на оба вопроса: (1) Какие существуют естественные представления о квантовых монотонных схемах? (2) Как бы выглядел квантовый результат в стиле Разборова на основе решетки?

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

Что мы хотим от кванта

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

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

Простая модель квантовых монотонных цепей

Рассмотрим модель контура, которая подразумевается в комментарии Цуёси Ито о «монотонных квантовых каналах» (и это почти то, что нужно делать, если нужно понятие «контура», которое не ограничивается унитарной эволюцией).

Пусть - пространство эрмитовых операторов на C 2 (так что оно содержит все операторы плотности на одном кубите). Как бы мы определили квантовый монотонный вентиль G : H aH bH c от двух входных кубитов a , b до выходного кубита c таким образом, чтобы он не был эффективно классическим монотонным вентилем? Я думаю, что просто сказать, что вывод не должен быть ограничен | 0 HC2G:HaHbHca,bcили | 1 |00|или их смеси; бушелейчто быть «монотонным», мы должны требоватьчтобыкачестве1 ||11|и 1|1|Tra(ρab)|1увеличение, значение1| G(ρ a b )| 1должен быть не убывает. Для шлюза с двумя входами-кубитами это означает, чтоGдолжен быть реализован в принципе как1|Trb(ρab)|11|G(ρab)|1G

  1. выполнение двухкубитного измерения относительно некоторого ортонормированного базиса , где | ц , | ν охватывают подпространство Хэмминга вес 1, и{|00,|μ,|ν,|11}|μ,|ν

  2. производя в качестве выходного сигнала некоторого состояния , соответствующего результату , что измеренного, где 1 | ρ 00 | 1 1 | ρ λ | 1 1 | ρ 11 | 1 для каждого .ρ{ρ00,ρμ,ρν,ρ11}1|ρ00|11|ρλ|11|ρ11|1λ{μ,ν}

Цепи - только составы их разумным способом. Мы могли бы также разрешить разветвление в виде схем, которые встраивают единообразно и ; мы должны как минимум разрешить эти карты на входе, чтобы позволить копировать каждый (номинально классический) входной бит.| 1 | 11 1 |0|000|1|111

Представляется разумным либо рассмотреть весь континуум таких ворот, либо ограничиться каким-то конечным набором таких ворот. Любой выбор порождает другую «основу квантовых монотонных затворов» для цепей; Можно рассмотреть, какими свойствами обладают разные монотонные основания. Состояния могут быть выбраны полностью независимо при условии ограничения монотонности; несомненно, было бы интересно (и, вероятно, практично связать ошибку) установитьиХотя я не вижу причин требовать этого в теории. Очевидно, AND и OR - это ворота этого типа, гдеа также ρ 00 = | 0 ρ00,ρμ,ρν,ρ11ρ 11 = | 1 ρ00=|00|ρ μ = ρ ν = | 0 ρ11=|11|ρ μ = ρ ν = | 1 ρμ=ρν=|00|| ц | N , ρμ=ρν=|11|соответственно, что бы вы ни выбрали или чтобы быть.|μ|ν

Для любой константы k можно также рассмотреть основания шлюзов, включая вентили k -input-one-output. Самый простой подход в этом случае, вероятно, состоит в том, чтобы разрешить gates который может быть реализован, как указано выше, позволяя любое разложение подпространств каждого веса Хэмминга и требовать, чтобы для каждогоG:HkHVwH2k0wk

max|ψVw1|G(|ψψ|)|1min|ψVw+11|G(|ψψ|)|1
0w<k . Не ясно, сколько дополнительной вычислительной мощности это даст вам (даже в классическом случае).

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

Квантовый вариант результата Разборова

Рассмотрим изложение Тимом Гауэрсом результатов Alon & Boppana (1987), Combinatorica 7, стр. 1–22, которые усиливают результаты Разборова (и разъясняют некоторые его приемы) для монотонной сложности CLIQUE. Гауэрс представляет это в терминах рекурсивной конструкции семейства множеств, начиная с «полупространств» логического куба для каждого . Если мы уберем привилегированное положение стандартного базиса в базовых наборах, по аналогии с локальной леммой Квантового Ловаша , мы можем рассмотреть подпространство 1 j n H n 2 n A jH n 2 A j = U j E j

Ej={x{0,1}n:xj=1}
1jnH2nсоответствовать бинарному предложению (принадлежит ли состояние подпространству или является ортогональным ему), которое может возникнуть в результате измерения. Например, мы можем рассмотреть подпространств заданных Допустим квантово-логические аналоги конъюнкции и дизъюнкции подпространств: nAjH2nAB = AB ; AB = A + B = { a + b
Aj=UjEj, for each 1jnwhere Ej:={|x:xEj};Uj:H2nH2n a unitary of bounded complexity.
AB=AB;AB=A+B={a+b:aA,bB}.
Затем мы спрашиваем, как долго требуется рекурсивное построение конъюнкций и дизъюнкций пространств для получения пространства , так что проектор на мало отличается от проектора на пространство, охватываемое индикаторными функциями графиков, имеющих клики размера ; например, чтобыCΠCCΠK(r)rΠCΠK(r)<1/poly(n), Монотонная часть участвует в квантовых логических операциях, и примитивные предложения о входе также являются квантовыми.

В общем случае существует проблема с обработкой этого как вычислительной проблемы: дизъюнкция не соответствует никаким знаниям, которые можно было бы с уверенностью получить путем измерений на конечном количестве копий с использованием измерений черного ящика для и один, если они не являются изображениями коммутирующих проекторов. Эта общая проблема все еще может рассматриваться как интересный результат о геометрическо-комбинаторной сложности и может привести к результатам, связанным с расстроенными локальными гамильтонианами. Однако может быть более естественным просто потребовать, чтобы подпространстваB A j U jABAjвозникают из коммутирующих проекторов, и в этом случае дизъюнкция является просто классическим ИЛИ результатов измерений этих проекторов. Тогда мы можем потребовать, чтобы все унитарные были одинаковыми, и это становится проблемой для унитарной схемы (которая порождает «примитивные события») с монотонной классической постобработкой (которая выполняет логические операции над этими событиями).Uj

Также обратите внимание, что если мы не налагаем никаких дополнительных ограничений на пространства , это может быть подпространство с очень высоким перекрытием с некоторым пространством охватываемым стандартными состояниями , это те двоичные строки, в которых .E k x ˉ E k x k =0AjEkxE¯kxk=0

  • Если эта возможность делает вас брезгливым, вы всегда можете потребовать, чтобы имел угол разделения от любого не менее (так что наши примитивные подпространства в худшем случае приблизительно смещены от подпространств, в которых один из битов установлен в 1).E k πAjEkπ21/poly(n)

  • Если мы не введем такое ограничение, мне кажется, что допущение подпространств, имеющих высокое перекрытие с будет препятствием для приближения CLIQUE (r) в любом случае; Либо мы были бы более или менее ограничены рассмотрением отсутствия определенного ребра (а не его наличия), либо мы были бы вынуждены полностью игнорировать одно из ребер. Итак, я не считаю крайне важным наложение каких-либо ограничений на , за исключением, возможно, того, что все они являются изображениями коммутирующего набора проекторов, если цель состоит в том, чтобы рассмотреть, как "монотонно оценивать CLIQUE из простых квантовых предложений ». В худшем случае это было бы классически равносильно тому, чтобы на входе не было вентилей NOT (и все отрицательные эффекты происходили после отрицания). A jEkAj

Опять же, мне не ясно, заменяет ли базовые наборы произвольными подпространствами более интересную проблему, чем просто использование подпространств ; хотя, если мы ограничимся случаем формул CNF (в коммутирующем или некоммутирующем случае), полученные результаты будут соответствовать некоторому понятию сложности гамильтониана без фрустраций, многообразие основного состояния которого состоит из стандартного базиса государства, представляющие клики.H2nEj

Ниль де Бодрап
источник
твой эскиз заставляет меня задуматься. Есть ли концепция монотонности для сложных ценностей? возможно, изучу реальные арифметические схемы еще немного. это может быть что-то простое, как<? или для двух входных комплексных вентилей и качестве входных данных, выходных данных,и? |x||y|x1x2y|y|>|x1||y|>|x2|
ВЗН
Ой, я ошибся ... Я планировал отдать награду Нилу, но щелкнул не в том месте. Я должен вам 200 репутации Ниль :).
Гил Калай
Есть ли способ, которым я могу передать его Нилу?
Джо Фицсимонс
@ Джо, ты можешь назначить новую награду за этот вопрос и присудить его Нилу.
Каве
@Kaveh: Хорошо, сделаем. Я не могу наградить его в течение 24 часов, но присужду его тогда.
Джо Фицсимонс
7

Как свидетельствуют комментарии Робина и Цуёси, понятие монотонных цепей, кажется, легко распространяется на квантовые цепочки.

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

Поскольку эволюция замкнутой квантовой системы является унитарной (которую мы можем предположить, дается ), то для любого состояния такого что существует альтернативное состояние такое что но для которого и, следовательно, эволюция не является монотонной.U|ψf(U|ψ)>f(|ψ)|ϕf(|ϕ)>f(|ψ)f(U|ψ)>f(U|ϕ)U

Таким образом, единственные схемы, которые являются монотонными относительно являются теми, которые для всех . Таким образом, любое множество ворот, которое является монотонным по отношению к , состоит из вентилей, которые коммутируют с .е ( U | г | ) = е ( | г | ) | г | е еff(U|ψ)=f(|ψ)|ψff

Очевидно, что множества вентилей, которые могут это удовлетворить, зависят от определения функции . Если постоянна, то все множества вентилей монотонны относительно нее. Однако, если мы выберем в качестве веса состояний Хэмминга в вычислительном базисе (несколько естественное расширение используемое в классическом случае), мы получим интересную структуру. Наложенное ограничение требует, чтобы вес Хэмминга оставался неизменным. Операции, которые сохраняют эту сумму, либо для диагональных операций, либо для частичных свопов, либо их комбинаций. Эта структура довольно часто проявляется в физике (в моделях сильной связи и т. Д.) И похожа на проблему бозон-рассеяния, изученную Ааронсоном и Архиповым.ф ф фffffхотя и не идентичны (это немного другая проблема рассеяния). Кроме того, он содержит схемы для IQP и, следовательно, не должен эффективно моделироваться классически.

Джо Фитцсимонс
источник
1
(1) Я не думаю, что ваше понятие «квантовый монотон» является обобщением понятия монотонности для классических булевых функций. Например, вентиль AND является монотонным, поскольку x_1 ≤ y_1 и x_2 ≤ y_2 подразумевают AND (x_1, x_2) ≤ AND (y_1, y_2), где x_1, x_2, y_1, y_2 ∈ {0,1}. Обратите внимание, что сравнение выполняется между двумя входами или между двумя выходами, а не между входом и выходом.
Tsuyoshi Ito
(2) На всякий случай я не сказал, что понятие монотонных цепей не так легко распространяется на квантовые цепочки (и я не говорил, что это так). Я только что сказал, что по сравнению со случаем обратимых цепей, где понятие монотонных цепей неинтересно, случай квантовых цепей неясен.
Tsuyoshi Ito
1
@JoeFitzsimons: Я думаю, что вес Хэмминга довольно хорошо фигурирует в требовании монотонности или (точнее), что свойство быть неубывающим, когда вы «включаете» биты от нуля до единицы, является как раз тем понятием, о котором заботятся компьютерные ученые когда они относятся к монотонным цепям. Вы могли бы рассмотреть варианты, где вычисляемая функция является неубывающей функцией некоторых вещественно-значимых функций строки битов, таких как ваше предложение по повторной индексации; но это также является значительным отклонением от того, что интересует компьютерных специалистов, за исключением случаев с сильной мотивацией.
Ниль де Бодрап,
1
Обычный частичный порядок в цепочках битов (поэлементное сравнение) выглядит гораздо более естественным, чем сравнивать их по весам Хэмминга со мной, но если вы считаете, что вес Хемминга естественен, я не буду спорить. Что касается третьего абзаца, мне все еще трудно следить за вашим аргументом, но я полагаю, что упускаю что-то простое, и мне просто нужно немного времени и свежий взгляд на это.
Цуёси Ито
1
@NieldeBeaudrap: я согласен. Я не хотел сказать, что думал иначе.
Джо Фицсимонс
-6

Вы задаете в основном два вопроса с сильно различающимися трудностями на границе двух больших полей, то есть булевых схем и вычислений QM, о возможности того, что иногда называют «теоремой мостика» в математике:

  • квантовый аналог монотонных цепей

  • квантовый аналог Разборова

короткий откровенный ответ - нет или не так далеко .

поскольку (1), не столь сложный вопрос, но, по-видимому, редко рассматриваемый, он обнаружил следующую ссылку, которую можно было бы использовать в литературе как соответствующий случай.

Твердость аппроксимации для квантовых задач Гарибианом и Кемпе

они рассматривают некоторые «монотонные» проблемы в квантовом контексте, например, QMSA, «Квантово-монотонное минимальное удовлетворяющее назначение, QMSA», то есть аналог SAT QM; (также другая проблема - Quantum Monotone Minimum Weight Word, QMW) и покажите некоторые результаты аппроксимации твердости, т.е. нижние границы. они не рассматривают монотонные квантовые схемы как таковые, но идея может состоять в том, что квантовую схему или алгоритм, который решает монотонную функцию QMSA, можно принять в качестве аналога QM.

что касается (2), это был бы очень продвинутый результат, если бы он существовал, который, по-видимому, не "пока". Thm Разборова в основном является результатом типа «узкого места» с нижней границей, который считается явным прорывом и практически не имеет аналогов в (монотонной) теории цепей.

грубо говоря, да, конечно, в QM-вычислениях обнаружены некоторые узкие места с нижней границей, например, связанные с прямыми теоремами о продукте.

Квантовые алгоритмы, нижние границы и пространственно-временные компромиссы от Spalek

однако, возможно, лучшая аналогичная нижняя граница вычисления QM установит нижнюю границу для числа операций кубита или, возможно, будет основана на «полных» гейтах, таких как вентили Тофоли для монотонной функции. Я не знаю о доказательствах этого типа.

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

ВЗН
источник
пс его также интересно отметить , что razborovs THM включает то , что иногда называют «аппроксиматором» цепи / ворота и твердость приближение, вероятно , / по- видимому , связано с концепцией аппроксиматором цепи / ворот способами , которые были нанесены на карту нету из ....
ВЗН
6
вместо того, чтобы добавлять комментарии, я бы беспокоился о 7-ти понижениях ...
Алессандро Косентино
2
??? виновен пока не доказан невиновен? =)
ВЗН