An Almost-Quadratic Lower Bound for Quantum Formula Size

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

We show that Nechiporuk's method for proving lower bound for Boolean formulas can be extended to the quantum case. This leads to an n^2 / log^2 n lower bound for quantum formulas computing an explicit function. The only known previous explicit lower bound for quantum formulas (by Yao) states that the majority function does not have a linear-size quantum formula.
14 pages, 6 figures

Keywords

Quantum Physics, Computational Complexity

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/94013

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/quant-ph/9903042
 http://arxiv.org/abs/quant-ph/9903042

Collections

arXiv