Quantum Formulas: a Lower Bound and Simulation

Simple item page
dc.creatorRoychowdhury, Vwani P.
dc.creatorVatan, Farrokh
dc.date2001-04-10
dc.date.accessioned2026-07-07T06:01:54Z
dc.date.available2026-07-07T06:01:54Z
dc.descriptionWe show that Nechiporuk's method for proving lower bounds 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 states that the majority function does not have a linear-size quantum formula. We also show that quantum formulas can be simulated by Boolean circuits of almost the same size.
dc.description22 pages, LaTeX, 6 figures. Final and extended version of quant-ph/9903042. To appear in SIAM Journal on Computing
dc.identifierhttps://arxiv.org/abs/quant-ph/0104053
dc.identifierhttp://arxiv.org/abs/quant-ph/0104053
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/89427
dc.subjectQuantum Physics
dc.subjectComputational Complexity
dc.titleQuantum Formulas: a Lower Bound and Simulation
dc.typetext

Files

Collections

arXiv