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
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.
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copiar
Hideaki FUKUHARA, Eiji TAKIMOTO, "Lower Bounds on Quantum Query Complexity for Read-Once Formulas with XOR and MUX Operators" in IEICE TRANSACTIONS on Information,
vol. E93-D, no. 2, pp. 280-289, February 2010, doi: 10.1587/transinf.E93.D.280.
Abstract: We introduce a complexity measure r for the class F of read-once formulas over the basis {AND,OR,NOT, XOR, MUX} and show that for any Boolean formula F in the class F, r(F) is a lower bound on the quantum query complexity of the Boolean function that F represents. We also show that for any Boolean function f represented by a formula in F, the deterministic query complexity of f is only quadratically larger than the quantum query complexity of f. Thus, the paper gives further evidence for the conjecture that there is an only quadratic gap for all functions.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.E93.D.280/_p
Copiar
@ARTICLE{e93-d_2_280,
author={Hideaki FUKUHARA, Eiji TAKIMOTO, },
journal={IEICE TRANSACTIONS on Information},
title={Lower Bounds on Quantum Query Complexity for Read-Once Formulas with XOR and MUX Operators},
year={2010},
volume={E93-D},
number={2},
pages={280-289},
abstract={We introduce a complexity measure r for the class F of read-once formulas over the basis {AND,OR,NOT, XOR, MUX} and show that for any Boolean formula F in the class F, r(F) is a lower bound on the quantum query complexity of the Boolean function that F represents. We also show that for any Boolean function f represented by a formula in F, the deterministic query complexity of f is only quadratically larger than the quantum query complexity of f. Thus, the paper gives further evidence for the conjecture that there is an only quadratic gap for all functions.},
keywords={},
doi={10.1587/transinf.E93.D.280},
ISSN={1745-1361},
month={February},}
Copiar
TY - JOUR
TI - Lower Bounds on Quantum Query Complexity for Read-Once Formulas with XOR and MUX Operators
T2 - IEICE TRANSACTIONS on Information
SP - 280
EP - 289
AU - Hideaki FUKUHARA
AU - Eiji TAKIMOTO
PY - 2010
DO - 10.1587/transinf.E93.D.280
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E93-D
IS - 2
JA - IEICE TRANSACTIONS on Information
Y1 - February 2010
AB - We introduce a complexity measure r for the class F of read-once formulas over the basis {AND,OR,NOT, XOR, MUX} and show that for any Boolean formula F in the class F, r(F) is a lower bound on the quantum query complexity of the Boolean function that F represents. We also show that for any Boolean function f represented by a formula in F, the deterministic query complexity of f is only quadratically larger than the quantum query complexity of f. Thus, the paper gives further evidence for the conjecture that there is an only quadratic gap for all functions.
ER -