FINDING PROBLEMS WITH POTENTIAL QUANTUM SUPREMACY USING GRAPHS.

The main motivation for the development of quantum algorithms is their advantages over classical algorithms. In this context, in a query complexity model we wish to compute a boolean function f : S → T , where S ⊆ Σⁿ and T is a finite set [2]. It is possible to discover new problem where quantum algorithms have a potential advantage over classical algorithms. This can be achieved by searching for linear polynomials of second degree, 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 0.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.

We say that a polinomial p aproximates a function f with error bounded by ϵ, if |p(x)−f (x)| < ϵ for all x in the domain of f . Furthermore, we know that if there exist a ϵ < 1 /2 and a ϵ′ < 1 /2 , such that a partial boolean function f can be aproximated by a degree − 2 polynomial with error bounded by ϵ if and only if f is computable by a 1−query quantum algorithm with error bounded by ϵ′ [1]

For each b ∈ {0, 1}ⁿ, we can define χ_b : {1, −1}ⁿ → {−1, 1} such that χ_b(x) =  the product of b_ix_i for all i. This family of functions is an orthonormal basis of the function space f : {1, −1} → R [4]. Given p : {1, −1}ⁿ → [0, 1] a multilinear polynomial of degree at most two, then p has a unique representation as a linear combination of these functions such that |b| ≤ 2.

Given this, we define a graph with no multiple edges G(V, E), where V and E are the sets of vertices and edges respectively and denote ω : E → R and x ∈ {1, −1}ⁿ⁺¹ (considering the ancilla bit x₀ = 1), we call D = (G, ω) Weighted dynamical graph (WDG) and define the value of D over x as the sum of the product of a function s(e,x) and ω over all the edges in E, where if e = (v_i, v_j ), then s(e, x) = x_ix_j and if e = (v_i), then s(e, x) = x₀x_i. And associated to D we define a (n + 1) × (n + 1) ral matrix M^D such that: (i) if i = 0 and i different from j, then M^D _i,j = 1 /2 ω({j}), (ii) if j = 0 and i different from j, then M^D _i,j = 1/ 2 ω({i}), (iii) if i = j, then M^D _i,j = 0, and (iv) if i, j > 0, then M^D _i,j = M^D _j,i = 1/ 2 ω({i, j}). Where g_D (x) = xM^Dx^t. The optimization problem we discussed earlier is defined here as follows:

Definition 0.1. Let f be a function such that f : S → [0, 1] and S ⊂ {1, −1}ⁿ. Considering a WDG D = (G, ω) and given some ϵ > 0: Find C and ω that maximize the sum of the sum of |ω(e)| over e∈E (the norm L1 in the WDG), subject to: (i) |gD (x) − f (x) + C| < ϵ for each x ∈ S, and (ii) δ(D) = 1. Where δ(D)  is the difference between the maximum and minimum values ​​of  g_D (x).  

 Now, consider the following terms:
• D and D′ be WGDs such that f (x) = (xM^Dx^t+K) and f ′(y) = (yM^D′y^t+K′) for K, K′ ∈ R, S ⊂ {1, −1}ⁿ and T ⊂ {1, −1}^m, where f : S → [0, 1] and f ′ : T → [0, 1]  respectively.
• Denote S⁺ = {x ∈ S : f (x) = 1}, S⁻ = {x ∈ S : f (x) = 0}, T ⁺ = {y ∈ T : f ′(y) = 1} and T ⁻ = {y ∈ T : f ′(y) = 0}.

if L(f ) be the fourier L1 norm of f over its descomposition on functions χb, we state the following theorem

Theorem 0.1. There is a WDG D′′ such that i) L(g_D′′ ) = (L(g_D ) + |K|)(L(g_D′ ) + |K′|) − |KK′| and ii) g_D′′ (x) = f ′′(x) + K′′ for x ∈ ((S⁺ ⊗ T ⁺) ∪ (S⁻ ⊗ T ⁻) ∪ (S⁺ ⊗ T ⁻) ∪ (S⁻ ⊗ T ⁺)) and some K′′ ∈ R. Where f ′′ : {1, −1}^nm → [0, 1] satisfies (a) f ′′(ω) = 1 if ω ∈ (S⁺ ⊗ T ⁺), and (b) f ′′(ω) = 0 if ω ∈ ((S⁺ ⊗ T ⁻) ∪ (S⁻ ⊗ T ⁺) ∪ (S⁻ ⊗ T ⁻)).

Here we show a relatively simple framework for problem search where single-query quantum algorithms can have potential advantage over classical decision trees. A possible strategy for developing quantum algorithms is to first solve the optimization problem using generic optimization methods, in order to generalize the algorithm through a sequence of WGDs obtained by applying the Theorem 0.1.

References
[1] Scott Aaronson, Andris Ambainis, J¯anis Iraids, Martins Kokainis, and Juris Smotrovs. “Polynomials, quantum query complexity, and Grothendieck’s inequality”. In: arXiv preprint arXiv:1511.08682 (2015).
[2] Howard Barnum, Michael Saks, and Mario Szegedy. “Quantum query complexity and semi-definite programming”. In: 18th IEEE Annual Conference on Computational Complexity, 2003. Proceedings. IEEE. 2003, pp. 179–193.
[3] Sebastián Alberto Grillo and Franklin de Lima Marquezino. “Fourier 1-norm and quantum speed-up”. In: Quantum Information Processing 18.4 (2019), p. 99.
[4] Ryan O’Donnell. Analysis of boolean functions. Cambridge University Press, 2014.