An Almost-Quadratic Lower Bound for Quantum Formula Size

Simple item page
dc.creatorRoychowdhury, Vwani P.
dc.creatorVatan, Farrokh
dc.date1999-03-11
dc.date.accessioned2026-07-07T06:16:17Z
dc.date.available2026-07-07T06:16:17Z
dc.descriptionWe 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.
dc.description14 pages, 6 figures
dc.identifierhttps://arxiv.org/abs/quant-ph/9903042
dc.identifierhttp://arxiv.org/abs/quant-ph/9903042
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/94013
dc.subjectQuantum Physics
dc.subjectComputational Complexity
dc.titleAn Almost-Quadratic Lower Bound for Quantum Formula Size
dc.typetext

Files

Collections

arXiv