2018-01-11
Quantum query algorithms are completely bounded forms
Publication
Publication
We prove a characterization of quantum query algorithms in terms of polynomials satisfying a certain (completely bounded) norm constraint. Based on this, we obtain a refined notion of approximate polynomial degree that equals the quantum query complexity, answering a question of Aaronson et al. (CCC’16). Using this characterization, we show that many polynomials of degree at least 4 are far from those coming from quantum query algorithms. Our proof is based on a fundamental result of Christensen and Sinclair (J. Funct. Anal., 1987) that generalizes the well-known Stinespring representation for quantum channels to multilinear forms. We also give a simple and short proof of one of the results of Aaronson et al. showing an equivalence between one-query quantum algorithms and bounded quadratic polynomials.
| Additional Metadata | |
|---|---|
| , , , | |
| doi.org/10.4230/LIPIcs.ITCS.2018.3 | |
| Leibniz International Proceedings in Informatics, LIPIcs | |
| Quantum and classical data transmission | |
| Innovations in Theoretical Computer Science Conference (ITCS) | |
| Organisation | Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands |
|
Arunachalam, S., Briët, J., & Palazuelos, C. (2018). Quantum query algorithms are completely bounded forms. In Innovations in Theoretical Computer Science Conference (pp. 3:1–3:21). doi:10.4230/LIPIcs.ITCS.2018.3 |
|
