Uma noção de circuitos quânticos monótonos

27

Na complexidade computacional, existe uma distinção importante entre cálculos monótonos e gerais e um famoso teorema de Razborov afirma que 3-SAT e até MATCHING não são polinomiais no modelo monótono de circuitos booleanos.

Minha pergunta é simples: existe um análogo quântico para circuitos monótonos (ou mais de um)? Existe um teorema quântico de Razborov?

Gil Kalai
fonte
10
Aqui estão meus dois centavos: O salto dos circuitos clássicos para os circuitos quânticos pode ser dividido em duas etapas ao adicionar circuitos reversíveis clássicos no meio. Circuitos reversíveis clássicos são aqueles em que apenas são permitidos portões reversíveis. Por exemplo, o portão de Toffoli é um portão universal para computação reversível. Não sei como definir a noção de monótono para esses circuitos. Parece-me que definir circuitos reversíveis clássicos monótonos é um pré-requisito para definir circuitos quânticos monótonos.
Robin Kothari
6
(1) Um circuito reversível (clássico) implementa uma bijeção em {0,1} ^ n, e claramente a única bijeção monotônica é o mapeamento de identidade. Portanto, não creio que seja razoável definir "circuitos reversíveis monótonos" de maneira não trivial.
Tsuyoshi Ito
3
(2) Não tenho certeza sobre o caso quântico. Se podemos definir "canais quânticos monótonos", será natural definir "circuitos quânticos monótonos" como circuitos quânticos cujo conjunto de portas é escolhido entre canais quânticos monótonos, assim como circuitos clássicos monotônicos são circuitos cujo conjunto de portas é escolhido entre funções monótonas .
Tsuyoshi Ito
2
@RobinKothari, TsuyoshiIto: A importância da reversibilidade para a computação quântica vem precisamente do caso especial da evolução de Schrödinger de um sistema fechado. Quando falamos dos portões AND e OR, no entanto, estamos considerando um sistema físico abstrato que é uma caricatura dos portões lógicos que estão nos computadores; e esses portões funcionam precisamente porque não são sistemas fechados. Se nos permitirmos falar dos portões AND e OR propriamente ditos, acho bastante razoável levantar a convenção de considerar sistemas fechados também para a questão computacional quântica.
Niel de Beaudrap 11/09/12
3
@Niel, Tsuyoshi: Acho que pensei que um circuito quântico monótono ainda seria um circuito quântico no sentido tradicional (ou seja, unitaristas seguidos por uma medição). Mas, seguindo o argumento de Niel, acho que faz sentido descartar essa restrição. Portanto, meu comentário anterior realmente não se aplica então.
Robin Kothari

Respostas:

17

Você está realmente fazendo duas perguntas diferentes e esperando que exista uma única resposta que responda a ambas: (1) Que noções naturais de circuitos monotônicos quânticos existem? (2) Como seria um resultado quântico no estilo Razborov baseado em treliça?

Não é óbvio como conseguir as duas coisas ao mesmo tempo, então descreverei o que para mim parece uma noção razoável de circuitos monotônicos quânticos (sem indicar se existe ou não um resultado Razborov correspondente) e uma noção completamente diferente de como seria uma conjectura quântica "natural" de Razborov (sem indicar se é provável que seja verdadeira).

O que queremos do quantum

Como observo nos comentários, acho que não é necessário tentar espremer a noção de circuitos monotônicos em um molde de unitariedade. Seja no fato de que a evolução com o tempo não precise preservar a base padrão, ou no fato de existir várias bases de medição nas quais os resultados podem ser enredados, acho que a condição sine qua non da computação quântica é o fato de que a base padrão não é a única base. Mesmo entre os estados do produto, em algumas implementações é definido apenas por uma opção de quadro de referência.

O que devemos fazer é considerar as coisas de maneira a remover a base padrão de seu lugar tradicional e privilegiado - ou, nesse caso, o máximo possível, mantendo uma noção significativa de monotonicidade.

Um modelo simples de circuitos monotônicos quânticos

Considere um modelo de circuito implícito no comentário de Tsuyoshi Ito sobre "canais quânticos monótonos" (e que é praticamente o que se deve fazer se se deseja uma noção de "um circuito" que não se restrinja à evolução unitária).

Seja o espaço dos operadores hermitianos em C 2 (para que ele contenha todos os operadores de densidade em um qubit). Como podemos definir um monótona portão quântico G : H umH bH c de dois entrada qubits um , b para uma saída qbit C , de tal maneira que não é efectivamente um portão monótona clássica? Eu acho que é fácil dizer que a saída não deve ser restrita a | 0 HC2G:HaHbHca,bcou | 1 |00|, ou misturas deles; bu que ser "monótona", devemos exigir que, como1 ||11|e 1|1|Tra(ρab)|1aumento, o valor de1| G(ρ a b )| 1deve ser não decrescente. Para um gate qubit de duas entradas, isso significa queGdeve ser implementável em princípio como1|Trb(ρab)|11|G(ρab)|1G

  1. executando uma medição de dois qubit com relação a alguma base ortonormal onde | u , | ν estendem o subespaço de peso de Hamming 1, e{|00,|μ,|ν,|11}|μ,|ν

  2. produzindo como saída algum estado correspondente ao resultado medido, onde para cada .ρ{ρ00,ρμ,ρν,ρ11}1|ρ00|11|ρλ|11|ρ11|1λ{μ,ν}

Os circuitos são apenas composições destes da maneira sensata. Também podemos permitir a dispersão, na forma de circuitos que incorporam unicamente e ; devemos pelo menos permitir esses mapas na entrada, para permitir que cada bit de entrada (nominalmente clássico) seja copiado.|0|000|1|111

Parece razoável considerar todo o continuum de tais portões ou restringir a alguma coleção finita de tais portões. Qualquer escolha gera uma "base de porta monotônica quântica" diferente para os circuitos; pode-se considerar quais propriedades diferentes bases monótonas possuem. Os estados podem ser escolhidos de forma completamente independente, sujeito à restrição de monotonicidade; seria indubitavelmente interessante (e provavelmente prático para erro vinculado) definire, embora não veja motivo para exigir isso na teoria. Obviamente AND e OR são portões desse tipo, ondeeρ00,ρμ,ρν,ρ11ρ00=|00|ρ11=|11|ρμ=ρν=|00|ρμ=ρν=|11|respectivamente, o que alguém escolher ou a ser.|μ|ν

Para qualquer constante k , pode-se considerar também as bases de portas, incluindo as portas k -input-one-output. A abordagem mais simples nesse caso provavelmente seria permitir gates que pode ser implementado como acima, permitindo qualquer decomposição dos subespaços de cada peso de Hamming , e exigir que para cadaG:HkHVwH2k0wk

max|ψVw1|G(|ψψ|)|1min|ψVw+11|G(|ψψ|)|1
0w<k . Não está claro quanto poder computacional adicional isso daria a você (nem mesmo no caso clássico).

Não sei se há algo interessante a dizer sobre esses circuitos além do caso clássico, mas essa me parece ser a definição mais promissora de candidato de um "circuito monotônico quântico".

Uma variante quântica do resultado de Razborov

Considere a exposição de Tim Gowers dos resultados de Alon e Boppana (1987), Combinatorica 7 pp. 1–22, que fortalecem os resultados de Razborov (e explicitam algumas de suas técnicas) para a complexidade monótona do CLIQUE. Gowers apresenta isso em termos de uma construção recursiva de uma família de conjuntos, observando os "semi-espaços" do cubo booleano para cada . Se removermos a posição privilegiada da base padrão nos conjuntos de bases, em analogia ao Lema Local Quantum Lovász , poderemos considerar um subespaço de

Ej={x{0,1}n:xj=1}
1jnH2ncorresponder a uma proposição binária (se um estado pertence ao subespaço ou é ortogonal a ele) que pode surgir da medição. Por exemplo, podemos considerar subespaços dados por Nós permitir que os quântica-lógico análogos de conjunção e disjunção de subespaços: nAjH2n
Aj=UjEj, for each 1jnwhere Ej:={|x:xEj};Uj:H2nH2n a unitary of bounded complexity.
AB=AB;AB=A+B={a+b:aA,bB}.
Em seguida, perguntamos por quanto tempo uma construção recursiva de conjunções e disjunções de espaços é necessária para obter um espaço , de modo que o projetor em difere apenas levemente do projetor no espaço medido pelas funções indicadoras de gráficos com panelinhas de tamanho ; por exemplo, para queCΠCCΠK(r)rΠCΠK(r)<1/poly(n). A parte monotônica está envolvida nas operações lógicas quânticas, e as proposições primitivas sobre a entrada também são quânticas.

No caso geral, há um problema em tratar isso como um problema computacional: a disjunção não corresponde a nenhum conhecimento que possa ser obtido com segurança por medições em um número finito de cópias usando medições de caixa preta para e sozinho, a menos que sejam imagens de projetores pendulares. Esse problema geral ainda pode ser tratado como um resultado interessante sobre a complexidade geometrico-combinatória e pode dar origem a resultados relacionados a hamilcionistas locais frustrados. No entanto, pode ser mais natural exigir apenas que os subespaçosABAjsurgem de projetores pendulares, caso em que a disjunção é apenas o OR clássico dos resultados de medição desses projetores. Então, podemos exigir que os unitários sejam todos iguais, e isso se torna um problema sobre um circuito unitário (que dá origem aos "eventos primitivos") com pós-processamento clássico monótono (que executa as operações lógicas nesses eventos).Uj

Observe também que, se não impormos mais restrições aos espaços , ele poderá ser um subespaço com sobreposição muito alta com algum espaço estendido pelos estados padrão , quais são as cadeias binárias nas quais .AjEkxE¯kxk=0

  • Se essa possibilidade o deixa enjoado, você sempre pode exigir que tenha um ângulo de separação de qualquer de pelo menos (para que nossos subespaços primitivos sejam, na pior das hipóteses, aproximadamente imparciais dos subespaços em que um dos bits está definido como 1).AjEkπ21/poly(n)

  • Se não impusermos essa restrição, parece-me que admitir subespaços com alta sobreposição com seria um obstáculo à aproximação de CLIQUE (r) de qualquer maneira; ou estaríamos mais ou menos restritos a considerar a ausência de uma aresta específica (em vez de sua presença), ou seríamos forçados a ignorar completamente uma das arestas. Portanto, não considero tão importante impor restrições a , exceto possivelmente todas elas serem imagens de um conjunto de projetores pendulares, se o objetivo de alguém é considerar como "avaliar monotonicamente o CLIQUE a partir de proposições quânticas simples " Na pior das hipóteses, isso seria classicamente permitir NÃO portas na entrada (e fazer com que toda a dispersão ocorresse após a negação).EkAj

Novamente, não está claro para mim se a substituição dos conjuntos de bases por subespaços arbitrários de gera um problema mais interessante do que apenas usar os subespaços ; embora, se nos restringirmos ao caso das fórmulas da CNF (no caso de deslocamento ou não), os resultados obtidos corresponderão a alguma noção de complexidade de um hamiltoniano sem frustração, cuja variedade de estado fundamental consistia em base padrão estados representando panelinhas.H2nEj

Niel de Beaudrap
fonte
seu desenho me faz pensar. existe um conceito de monotonicidade para valores complexos? talvez estudará os papéis reais dos circuitos aritméticos um pouco mais. poderia ser algo simples como<? ou para um portão complexo de duas entradas e como entradas, saída,e? |x||y|x1x2y|y|>|x1||y|>|x2|
vzn
Ops, cometi um erro ... planejei dar a recompensa a Niel, mas cliquei no lugar errado. Devo-lhe 200 reputações Niel :).
Gil Kalai
Existe alguma maneira de passar para Niel?
Joe Fitzsimons
@ Joe, você pode colocar uma nova recompensa na questão e conceder a Niel.
Kaveh #
@ Kaveh: Ok, vai fazer. Não posso premi-lo por 24 horas, mas o premio então.
Joe Fitzsimons
7

Como evidenciado pelos comentários de Robin e Tsuyoshi, a noção de circuitos monótonos parece ser facilmente extensível a circuitos quânticos.

Para ter uma definição significativa de circuito monotônico quântico, precisamos escolher uma ordem em estados quânticos com relação aos quais a monotonicidade é definida. Classicamente, uma opção razoável (e que leva à noção normal de circuitos monotônicos) é o peso de Hamming, mas vamos considerar uma ordem dada por uma função arbitrária .f

Como a evolução de um sistema quântico fechado é unitária (o que podemos assumir é dado por ), então para cada estado modo que existe um estado alternativo tal que mas para o qual e, portanto, a evolução não é monotônica.U|ψf(U|ψ)>f(|ψ)|ϕf(|ϕ)>f(|ψ)f(U|ψ)>f(U|ϕ)U

Assim, os únicos circuitos monotônicos em relação a são aqueles que para todos . Assim, qualquer conjunto de portas que seja monotônico em relação a é composto por portões que comutam com .ff(U|ψ)=f(|ψ)|ψff

Obviamente, os conjuntos de portas que podem satisfazer isso dependem da definição de . Se for constante, todos os conjuntos de portas serão monotônicos em relação a ela. No entanto, se escolhermos como o peso de Hamming dos estados na base computacional (uma extensão um tanto natural do usada no caso clássico), obteremos uma estrutura interessante. A restrição imposta exige que o peso de Hamming permaneça inalterado. As operações que preservam esse valor são operações diagonais ou SWAPs parciais ou combinações deles. Essa estrutura aparece frequentemente na física (em modelos de ligação rígida etc.) e é semelhante ao problema de espalhamento do bóson estudado por Aaronson e Arkhipovffff, embora não seja idêntico (é um problema de dispersão ligeiramente diferente). Além disso, ele contém circuitos para IQP e, portanto, não deve ser eficientemente simulável classicamente.

Joe Fitzsimons
fonte
1
(1) Eu não acho que sua noção de “quantum monotone” seja uma generalização da noção de monotonicidade para funções booleanas clássicas. Por exemplo, a porta AND é monótona porque x_1 ≤ y_1 e x_2 ≤ y_2 implicam AND (x_1, x_2) ≤ AND (y_1, y_2), em que x_1, x_2, y_1, y_2 0,1 {0,1}. Observe que a comparação é entre duas entradas ou entre duas saídas, não entre entrada e saída.
Tsuyoshi Ito
(2) Apenas no caso, eu não disse que a noção de circuitos monótonos não se estende facilmente aos circuitos quânticos (nem eu disse que sim). Acabei de dizer que, comparado ao caso de circuitos reversíveis, onde a noção de circuitos monótonos é desinteressante, o caso de circuitos quânticos não é claro.
Tsuyoshi Ito
1
@ JoeFitzsimons: Eu acho que o peso de Hamming figura bastante bem no requisito de monotonicidade, ou (mais precisamente) que a propriedade de não diminuir quando você "liga" bits de zero a um é precisamente a noção que os cientistas da computação se preocupam quando se referem a circuitos monotônicos. Você pode considerar variações em que a função calculada é uma função não decrescente de alguma função de valor real das cadeias de bits, como sua proposta de reindexação; mas isso também é um desvio significativo do interesse dos cientistas da computação, exceto em casos fortemente motivados.
Niel de Beaudrap 19/09/12
1
A ordem parcial usual das strings de bits (a comparação elementar) parece muito mais natural do que compará-las com seus pesos de Hamming para mim, mas se você acha que o peso de Hamming é natural, não discutirei. Quanto ao terceiro parágrafo, ainda tenho dificuldade em seguir seu argumento, mas acho que estou perdendo algo simples e só preciso de um tempo e de uma nova olhada nele.
Tsuyoshi Ito
1
@NieldeBeaudrap: Eu concordo. Não quis sugerir que pensasse o contrário.
Joe Fitzsimons
-6

você faz basicamente duas perguntas de dificuldade amplamente divergente, na fronteira de dois grandes campos, ou seja, circuitos booleanos e computação QM, sobre a possibilidade do que às vezes é chamado de "teorema da ponte" em matemática:

  • análogo quântico de circuitos monótonos

  • análogo quântico de Razborovs thm

a resposta franca curta é não ou não tão longe .

para (1), não uma pergunta tão difícil, mas ainda aparentemente raramente considerada, apresentou a seguinte referência, que pode ser tomada como um caso relacionado na literatura.

Dureza de aproximação para problemas quânticos por Gharibian e Kempe

eles consideram alguns problemas "monótonos" em um contexto quântico, por exemplo, QMSA, "Atribuição Mínima de Satisfação Quântica Monotônica, QMSA", ou seja, um analógico SAT QM; (também outro problema, Palavra Mínima de Peso Mínimo Monotônico, QMW) e mostra alguns resultados de dureza de aproximação, ou seja, limites mais baixos. eles não consideram circuitos quânticos monótonos per se, mas uma idéia pode ser que um circuito ou algoritmo quântico que resolva a função monótona QMSA possa ser tomado como um analógico QM.

quanto a (2), seria um resultado muito avançado se existisse, o que não parece "até agora". O thm de Razborov é basicamente um resultado do tipo "gargalo" de limite inferior considerado um avanço distinto e um resultado quase incomparável na teoria de circuitos (monótonos).

então, grosso modo, sim, é claro que existem alguns gargalos de limite inferior encontrados na computação QM, por exemplo, relacionados a teoremas diretos de produtos, para uma pesquisa, veja

Algoritmos quânticos, limites inferiores e trocas de espaço e tempo por Spalek

no entanto, sem dúvida, um limite inferior de computação QM análogo melhor colocaria um limite inferior no número de operações de qubit ou possivelmente baseado em portas "completas", como portas de Toffoli, para uma função monótona. não conheço provas desse tipo.

outra abordagem pode limitar a análise a portões quânticos especiais AND e OR com bits adicionais "ancilla" adicionados para tornar os portões reversíveis.

vzn
fonte
ps também é interessante notar que razborovs thm envolve o que às vezes é chamado de circuitos / portões "aproximadores" e a dureza da aproximação provavelmente / aparentemente está conectada ao conceito de circuito / portão aproximador de maneiras que não foram mapeadas ....
vzn
6
em vez de adicionar comentários, eu me preocuparia com os 7 votos negativos ...
Alessandro Cosentino
2
??? culpado até que se prove inocente? =)
vzn 19/09/12