| | |
| | |
Stat |
Members: 3643 Articles: 2'487'895 Articles rated: 2609
28 March 2024 |
|
| | | |
|
Article overview
| |
|
Quantum Formulas: a Lower Bound and Simulation | Vwani P. Roychowdhury
; Farrokh Vatan
; | Date: |
10 Apr 2001 | Subject: | Quantum Physics; Computational Complexity | quant-ph cs.CC | Abstract: | We show that Nechiporuk’s method for proving lower bounds for Boolean formulas can be extended to the quantum case. This leads to an $Omega(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. | Source: | arXiv, quant-ph/0104053 | Services: | Forum | Review | PDF | Favorites |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser claudebot
|
| |
|
|
|
| News, job offers and information for researchers and scientists:
| |