Finding Problems with Potential Quantum Supremacy
using Graphs
Abstract
The main motivation for developing quantum algorithms is their advantage over classical counterparts. In a query complexity model we wish to compute a boolean function f : S → T, where S ⊆ Σn and T is a finite set [2]. It is possible to discover new problems with quantum advantage searching for second-degree linear polynomials, bounded between 0 and 1, which have a high L1 norm [3]. This situation can be represented by defining an optimization problem, where L1 is maximized for a proposed formulation of single-query quantum algorithms (which we denote as WDG). In this sense, in Theorem 1 an iterative method was presented, which produces a sequence of algorithms with increasing spectral normal L1 from algorithms with spectral norm L1 greater than 1. These contributions are detailed in the following paragraphs. [...]
Downloads
References
S. Aaronson, A. Ambainis, J. Iraids, M. Kokainis, and J. Smotrovs. “Polynomials, quantum query complexity, and Grothendieck’s inequality”. In: arXiv preprint arXiv:1511.08682 (2015).
H. Barnum, M. Saks, and M. Szegedy. “Quantum query complexity and semi-definite programming”. In: 18th IEEE Annual Conference on Computational Complexity, 2003. Proceedings. IEEE. 2003, pp. 179–193. doi: 10.1109/CCC.2003.1214419.
S. Alberto Grillo and F. de Lima Marquezino. “Fourier 1-norm and quantum speed-up”. In: Quantum Information Processing 18.4 (2019), p. 99. doi: https://doi.org/10.1007/s11128-019-2208-7.
R. O’Donnell. Analysis of boolean functions. Cambridge University Press, 2014. doi: https://doi.org/10.1017/CBO9781139814782.
