Usando o poder extra do método adversário negativo

17

O método adversário negativo ( ) é um SDP que caracteriza a complexidade da consulta quântica. É uma generalização do método adversário amplamente utilizado ( ) e supera as duas barreiras que impediram o método adversário:UMADV±UMADV

  1. A barreira do teste de propriedades: se todas as instâncias 0 estiverem distantes de todas as instâncias 1, o método adversário não poderá provar um limite inferior melhor que .ϵΩ(1 1/ϵ)

  2. A barreira da complexidade do certificado: se é a complexidade do certificado de instâncias , o método adversário não pode provar um limite inferior melhor que em queCb(f)bC0 0(f)C1 1(f)

No artigo original da , os autores constroem uma função de exemplo para a qual seu método supera as duas barreiras. No entanto, não vejo exemplos de problemas naturais em que isso tenha gerado novos limites inferiores.UMADV±

Você pode fornecer referências onde o método adversário negativo foi usado para atingir um limite inferior que o método original não pôde atingir?

O maior interesse para mim é o teste de propriedades. Atualmente, existem muito poucos limites mais baixos nos testes de propriedades, na verdade, eu só conheço dois ( CFMdW2010 , ACL2011 ), que usam o método polinomial (o primeiro por redução do problema de colisão que era originalmente delimitado pelo método polinomial). Sabemos que existem propriedades que requerem consultas quânticas para verificar qualquer computável (combinando os resultados em BNFR2002 e GKNR2009 ). Por que é tão difícil usar o método adversário negativo para provar limites mais baixos neles?Θ(f(n))f(n)∈O(n)Ω(f(n))

cc.complexity-theory reference-request quantum-computing query-complexity property-testing Artem Kaznatcheev
fonte
11
Na barreira de teste de propriedades, você provavelmente quer dizer vez de Ω ( 1 / n ) . Ω(1 1/ϵ)Ω(1 1/n)
Robin Kothari
5
Conheço uma aplicação do adversário negativo em criptografia por Brassard, Hoyer, Kalach, Kaplan, Laplante e Salvail ( iacr.org/conferences/crypto2011/abstracts/385.htm ) que aparecerá no CRYPTO'11. Eles usaram o teorema da composição para provar uma lacuna nos jogos de Merkle para um adversário quântico trabalhando contra partes quânticas trocando uma mensagem. Infelizmente, ainda não há uma versão final do artigo. Talvez você possa esperar pelo processo ou entrar em contato com os autores.
Marcos Villagra
o artigo que mencionei no meu comentário acima pode ser baixado do arXiv ( arxiv.org/abs/1108.2316 ). Em particular, verifique o lema 1 e o lema 5 no apêndice.
Marcos Villagra

Respostas:

2

Aparentemente, não posso comentar, portanto, isso será uma resposta, mesmo que seja apenas uma resposta parcial.

Elemento-nitidez tem um limite inferior de e a sua complexidade certificado é √Ω(N2/3) , portanto, se alguém tentar provar isso usando o método adversário, ele precisará usar o método adversário com pesos negativos (o que é ótimo) ou por que não o método adversário multiplicativo.N

Caso contrário, o método polinomial às vezes é mais fácil de usar que os métodos adversários, pois é suficiente para provar a existência de polinômios, enquanto que para o método adversário, você precisa explicitamente de ter uma boa matriz adversária e calcular sua norma de operador.

Loïck
fonte
Isso especificamente não responde à pergunta. Podemos usar o rigor do método do adversário negativo para saber que alguma matriz do adversário DEVE existir para problemas como distinção de elementos (ou se queremos testes de propriedades, problemas de colisão). Mas isso não é realmente usar o método adversário negativo, é usar o método polinomial. Eu acho que se a pergunta não estiver clara o suficiente, eu devo refinar.
Artem Kaznatcheev