Algoritmos quânticos com aceleração exponencial podem ser rederivados usando programas span?

12

Sabe-se agora que o limite inferior do adversário geral caracteriza a complexidade da consulta quântica devido ao trabalho inovador de Reichardt et al. A mesma linha de trabalho também estabelece conexões com a estrutura do programa span para projetar algoritmos quânticos.

Muitos algoritmos quânticos interessantes, incluindo aqueles com aceleração exponencial como o algoritmo de Simon e o algoritmo de Shor para encontrar períodos, podem ser expressos no modelo de consulta quântica.

Existe algum trabalho mostrando limites inferiores para esses algoritmos no modelo geral de adversários? Existe algum trabalho derivando os algoritmos de Simon ou Shor na estrutura do programa span?

Aparentemente, apenas algoritmos quânticos com aceleração polinomial, como os de Grover, foram re-derivados usando a estrutura de programas de extensão (ou gráfico de aprendizado de Belov).

Há trabalho de Korian et al. mostrando limites inferiores para Simon usando o método polinomial, mas aparentemente não há uma maneira conhecida de converter limites inferiores do método polinomial para limites inferiores do adversário geral.

preto
fonte
3
Eu votei acidentalmente para fechar como "fora de tópico" porque pensei que estava votando em uma pergunta diferente e cliquei na guia errada. Eu acho que essa é uma ótima pergunta e perfeitamente sobre o assunto , mas o sistema não me permite retirar meu voto acidental.
Artem Kaznatcheev

Respostas:

8

Eu acho que há pelo menos três perguntas na sua pergunta. Eu não tenho uma resposta satisfatória para todos eles, então essa não é uma resposta completa. Espero que haja mais respostas que respondam a todas as suas perguntas.

A pergunta no título: Algoritmos quânticos com aceleração exponencial podem ser rederividos usando programas span?

Como você observou, o limite geral do adversário caracteriza a complexidade da consulta quântica de todos os problemas de decisão, incluindo problemas promissores para os quais temos acelerações exponenciais. Portanto, em princípio, existe um programa span que resolve o problema de subgrupos ocultos abelianos, que é o problema de consulta usado nos algoritmos de Simon e Shor. Mas se existe um programa explícito de extensão para essa é sua próxima pergunta.

Existe algum trabalho derivando os algoritmos de Simon ou Shor na estrutura do programa span?

Eu não ouvi nenhum desses resultados. Não conheço um programa de extensão para o problema de Simon ou qualquer outro AHSP.

Existe uma maneira de converter limites inferiores do método polinomial em limites inferiores do adversário geral?

Sim, acredito que exista. Não consigo encontrar o artigo que tenha esse resultado, mas posso fornecer um link para uma palestra de Jérémie Roland . No resumo da palestra, ele diz o seguinte:

... Mais precisamente, mostraremos que o método do adversário multiplicativo, uma variação do método do adversário original, generaliza não apenas o método do adversário generalizado, mas também o método polinomial, de modo que engloba essencialmente todos os métodos conhecidos de limite inferior. Portanto, isso fornece uma abordagem construtiva para converter limites inferiores polinomiais na estrutura do método adversário.

Atualização : O artigo já está disponível online: Relação explícita entre todas as técnicas de limite inferior para a complexidade quântica de consultas por Loïck Magnin e Jérémie Roland

Robin Kothari
fonte
2
Eu só quero apontar algo aqui. Se o objetivo é reduzir o limite inferior do algoritmo de Simon usando o método polinomial, transformá-lo em um adversário e transformá-lo novamente em um algoritmo de gráfico de aprendizado, isso provavelmente não funcionaria. (Se fosse eu, eu o encontraria diretamente na estrutura do gráfico de aprendizado). Nossa redução é do método polinomial para o método multiplicativo do adversário (que é mais forte que o aditivo geral). Não conheço uma conexão com programas de extensão, pois o método multiplicativo do adversário não é um SDP.
Loïck
1
@ Loïck: Certo. Mesmo que seja encontrada a matriz adversa aditiva ideal para o problema de Simon, não está claro como construir um programa de extensão (ou gráfico de aprendizado) para isso.
22612 Robin Kothari