From the sum-of-squares representation of a Boolean function to an optimal exact quantum query algorithm
- 12 January 2021
- journal article
- research article
- Published by Springer Science and Business Media LLC in Quantum Information Processing
- Vol. 20 (1), 1-55
- https://doi.org/10.1007/s11128-020-02975-0
Abstract
No abstract availableKeywords
Funding Information
- NSFC (61572532)
This publication has 23 references indexed in Scilit:
- On Exact Quantum Query ComplexityAlgorithmica, 2013
- Quantum Algorithm for Linear Systems of EquationsPhysical Review Letters, 2009
- Quantum algorithms for the ordered search problem via semidefinite programmingPhysical Review A, 2007
- A Sum of Squares Approximation of Nonnegative PolynomialsSIAM Journal on Optimization, 2006
- Complexity measures and decision tree complexity: a surveyTheoretical Computer Science, 2002
- Quantum lower bounds by polynomialsJournal of the ACM, 2001
- The homology of certain subgroups of the symmetric group with coefficients in
L ie(n)Journal of Pure and Applied Algebra, 1998 - 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
- Quantum theory, the Church–Turing principle and the universal quantum computerProceedings of the Royal Society of London. Series A - Mathematical and Physical Sciences, 1985