A funcionalidade de pesquisa está em construção.
A funcionalidade de pesquisa está em construção.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

Lower Bounds on Quantum Query Complexity for Read-Once Formulas with XOR and MUX Operators Limites inferiores na complexidade da consulta quântica para fórmulas de leitura única com operadores XOR e MUX

Hideaki FUKUHARA, Eiji TAKIMOTO

  • Exibições de texto completo

    0

  • Cite isto

Resumo:

Introduzimos uma medida de complexidade r para a aula F de fórmulas de leitura única sobre a base {AND,OR,NOT, XOR, MUX} e mostre que para qualquer fórmula booleana F na aula F, r(F) é um limite inferior na complexidade da consulta quântica da função booleana que F representa. Também mostramos que para qualquer função booleana f representado por uma fórmula em F, a complexidade determinística da consulta de f é apenas quadraticamente maior que a complexidade da consulta quântica de f. Assim, o artigo fornece mais evidências para a conjectura de que existe uma única lacuna quadrática para todas as funções.

Publicação
IEICE TRANSACTIONS on Information Vol.E93-D No.2 pp.280-289
Data de publicação
2010/02/01
Publicitada
ISSN online
1745-1361
DOI
10.1587/transinf.E93.D.280
Tipo de Manuscrito
Special Section PAPER (Special Section on Foundations of Computer Science)
Categoria

autores

Palavra-chave