A Reformulation of The Quantum Query Model

O modelo de Quantum Query (QQM) e uma ferramenta importante para a análise e desenvolvimento de algoritmos quânticos. Este modelo generaliza árvores de decisão, com a complexidade sendo definida pelo número mínimo de consultas a um oráculo a fimm de calcular uma função definida para toda cadeia binária de seu domínio. Neste modelo são definidas medidas de complexidade para algoritmos de erro limitado e exatos. Desse modo, usam-se tais medidas para estudar a relação entre algoritmos de erros limitados e algoritmos exatos na computação clássica e quântica. Há várias questões abertas em relação a essas medidas, estimadas principalmente usando métodos de limite inferior.

A falta de abordagens para a construção de algoritmos quânticos é especialmente perceptível para o caso exato. Em contraste, vários resultados ótimos foram encontrados para algoritmos de erro limitado. Alguns resultados importantes são obtidos por reformulações do QQM usando modelos equivalentes, tais como span programs. Nesse sentido, o caso exato é menos compreendido do que os algoritmos de erro limitado. Neste trabalho propomos uma nova formulação para o QQM, chamada Formulação de Block Set (BSF), dando uma perspectiva alternativa para a análise de algoritmos quânticos exatos. Com esta formulação provamos um novo teorema de limite inferior para algoritmos quânticos exatos.

Usando algumas ideias da BSF, definimos uma simulação de algoritmos quânticos exatos por meios clássicos. A análise desta simulação nos dá uma condição necessária para acelerar a consulta quântica para algoritmos de erro limitado. Esta condição implica altos valores para uma norma-L1 definida sobre a probabilidade de saída do algoritmo. A partir desta condição, obtemos outras condições necessárias adaptadas dentro da BSF.