Lower bounds of quantum black-box complexity and degree of approximating polynomials by influence of Boolean variables
- 31 July 2000
- journal article
- research article
- Published by Elsevier in Information Processing Letters
- Vol. 75 (1-2) , 79-83
- https://doi.org/10.1016/s0020-0190(00)00069-7
Abstract
No abstract availableAll Related Versions
This publication has 9 references indexed in Scilit:
- Limit on the Speed of Quantum Computation in Determining ParityPhysical Review Letters, 1998
- Pseudo-average block sensitivity equals average sensitivityInformation Processing Letters, 1998
- Tight Bounds on Quantum SearchingFortschritte der Physik, 1998
- On the Power of Quantum ComputationSIAM Journal on Computing, 1997
- Sensitivity vs. block sensitivity (an average-case study)Information Processing Letters, 1996
- Sensitivity vs. block sensitivity of Boolean functionsCombinatorica, 1995
- On the degree of boolean functions as real polynomialscomputational complexity, 1994
- Rapid solution of problems by quantum computationProceedings of the Royal Society of London. Series A: Mathematical and Physical Sciences, 1992
- On the Influence of Single Participant in Coin Flipping SchemesSIAM Journal on Discrete Mathematics, 1988