dorsal/arxiv
View SchemaAn Almost-Quadratic Lower Bound for Quantum Formula Size
| Authors | Vwani P. Roychowdhury, Farrokh Vatan |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/9903042 |
| URL | https://arxiv.org/abs/quant-ph/9903042 |
Abstract
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.
{
"annotation_id": "8bd7d737-7d89-452b-a382-cf6946640aa3",
"date_created": "2026-03-02T18:02:44.537000Z",
"date_modified": "2026-03-02T18:02:44.537000Z",
"file_hash": "741810d9c6549ec11ffd952ed2e12fad286c96b844d76760b96f856285e72624",
"private": false,
"record": {
"abstract": "We show that Nechiporuk\u0027s method for proving lower bound for Boolean formulas\ncan be extended to the quantum case. This leads to an n^2 / log^2 n lower bound\nfor quantum formulas computing an explicit function. The only known previous\nexplicit lower bound for quantum formulas (by Yao) states that the majority\nfunction does not have a linear-size quantum formula.",
"arxiv_id": "quant-ph/9903042",
"authors": [
"Vwani P. Roychowdhury",
"Farrokh Vatan"
],
"categories": [
"quant-ph",
"cs.CC"
],
"title": "An Almost-Quadratic Lower Bound for Quantum Formula Size",
"url": "https://arxiv.org/abs/quant-ph/9903042"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "cd1baad2-2adc-4282-87e5-81d24d39c749",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}