Fourier 1-norm and quantum speed-up

Abstract

Understanding quantum speed-up over classical computing is fundamental for the development of efficient quantum algorithms. In this paper, we study such problem within the framework of the quantum query model, which represents the probability of output $x \in \{0,1\}^n$ as a function $\pi (x)$. We present a classical simulation for output probabilities $\pi$, whose error depends on the Fourier 1-norm of $\pi$. Such dependence implies upper-bounds for the quotient between the number of queries applied by an optimal classical algorithm and our quantum algorithm, respectively. These upper-bounds show a strong relation between Fourier 1-norm and quantum parallelism. We show applications to query complexity.

1 Introduction

A primary motivation in quantum computing is obtaining algorithms that solve problems much faster than the best classical counterparts. The quantum and classical decision tree models allow us to prove the existence of quantum speed-up in relation to classical query for several problems [6, 17, 27]. Query problems can be formulated as computing Boolean functions from inputs in $\{0,1\}^{n}$, with complexity being defined as the number of queries to the input, ignoring other computations [12]. This implies an important simplification of the analysis in comparison with problems formulated by Turing machines, where separations between complexity classes are usually much harder to prove [2]. Several quantum algorithms can be formulated within query models,¹ thus this formalism is powerful enough for analyzing important algorithms, such as search algorithms [1] or even non-query algorithms as Shor’s algorithm [3].

A complete understanding of quantum speed-up implies determining where and how it occurs. Thus, we can study such question from two distinct approaches: determining which functions or which algorithms allow a gap between quantum and classical computing. The first approach is intensively used in quantum query complexity, where effort is mainly invested in obtaining bounds for complexity measures and checking their tightness [1, 12]. The second approach is commonly implemented by identifying which quantum features are hard to simulate within classical sources [5]. One of the earliest attempts to explain quantum advantage is the discussion of quantum parallelism in quantum algorithms [16].

A well-studied quantum feature is quantum entanglement [20], which has been identified as a necessary condition for quantum speed-up in pure-state algorithms [21]. At the same time, the study of quantum entanglement depends on whether pure or mixed quantum states are allowed [14] and the measure defined for such entanglement [21, 29]. As an example of a widely applied entanglement measure, we can consider the size of partitions that describe product states in the quantum algorithm. If the size of the subsets in those partitions is upper-bounded by a constant through all the steps of the quantum algorithm, then it has an efficient classical simulation [21]. In addition, we can analyze the entanglement in a quantum state by measuring the Schmidt rank, where a polynomial upper-bound for this measure implies a polynomial classical simulation [29]. Using a model previously defined by Knill and Laflamme [22], different conditions for quantum speed-up were also identified. Such conditions are formulated on quantum correlations that are analyzed by a measure known as quantum discord [13]. A recent proposal comes from no-go theorems, identifying contextuality [11, 23] as a necessary condition for quantum speed-up—this condition presents an inequality violation in contrast to the other conditions based on measures [19]. The identification of necessary conditions for quantum advantages is an important issue for theoretical purposes and for the design of better quantum algorithms, specially if the conditions can be monitored in our design. Summarizing, a general goal in this line of research is to obtain sufficient and necessary conditions for quantum speed-up.

The present work offers a new perspective about speed-up produced by quantum algorithms in the quantum query model (QQM), which is the quantum generalization for decision tree models. First, we consider that the probability of obtaining a given output is a linear combination of orthonormal functions, where such set of functions is denoted as Fourier basis [15]. This approach is usually referred to as analysis of Boolean functions and has several results in quantum query and computer science [24,25,26, 28]. Using such representation of the output probability, we define a classical simulation of the quantum algorithm. The idea of our simulation is implementing minor simulations for parity functions from the Fourier basis, where each simulated function appears in the Fourier decomposition of the output probability. Similarly to related works in the context of quantum entanglement or quantum discord, in this paper we follow a strategy known as dequantization [5], which consists in analyzing how hard is the simulation of some algorithm in relation to a given measure. We prove that the error in our simulation depends on the $L_{1}$ norm defined over the Fourier basis, where such norm is computed for the output probability. Thereby, a necessary property for a hard classical simulation of a given quantum algorithm is having a large Fourier 1-norm for its output probability functions. This necessary condition is formalized as an upper-bound for the quotient between the number of queries of an optimal classical algorithm and of the simulated quantum algorithm, respectively. Notice that a well-designed algorithm in the QQM setting should maximize such quotient.

The state of any algorithm in the QQM can be described as a sum of vectors whose phase change depends on the input. The phase of each of these vectors may depend on different values from input, which shows quantum parallelism in action [18]. We show that the minimum size and the number of such vectors limit the value of the Fourier 1-norm, which allows alternative necessary conditions for quantum speed-up. The Fourier 1-norm is maximized by the homogeneity on the size of the vectors, which implies that simulating such balanced probabilities can be expensive by classical means. Therefore, our results give more formalism to the notion of quantum parallelism. Finally, we show applications of our results on (1) upper-bounds for randomized query, (2) lower-bounds for exact quantum query, and (3) polynomial simulation by randomized query.

We interpret the Fourier 1-norm as a measure for the quantity of Walsh functions that are “compressed” into the output probability function. The Walsh functions can be seen as individual computations in quantum query parallelism. Our intuition is that Fourier 1-norm is the amount of quantum parallelism on the output, and that quantum parallelism has potentially a quadratic influence on the relation between classical and quantum query complexities. Another reason for preferring the Fourier 1-norm over other measures is the possibility of controlling this parameter on a family of bound degree polynomials. We believe this can be an alternative strategy for the design of quantum algorithms with speed-up over the classical counterparts.

This work is structured as follows. In Sect. 2, we introduce preliminary formulations and theorems about the QQM. In Sect. 3, we describe a classical simulation of quantum algorithms. In Sect. 4, we present the upper-bounds from our simulation. In Sect. 5, we present alternative applications of our results. In Sect. 6, we present our conclusion.

2 Preliminary notions

The QQM [9] describes algorithms computing functions whose domain is a subset of $\left\{ 0,1\right\} ^{n}$. We describe the states and operations within such model, over a Hilbert space $\mathcal {H}$ with basis states $\left| i\right\rangle \left| j\right\rangle$, where $i\in \left\{ 0,1,\ldots ,n\right\}$ and $j\in \left\{ 1,\ldots ,m\right\}$, for an arbitrary m. The query operator is defined as $O_{x}\left| i\right\rangle \left| j\right\rangle =\left( -1\right) ^{x_{i}}\left| i\right\rangle \left| j\right\rangle$, where $x \equiv x_0 x_1 \cdots x_n$ is the input, and $x_{0} \equiv 0$. The final state of the algorithm over input x is defined as $\left| \Psi _{x}^{f}\right\rangle =U_{t}O_{x}U_{t-1}\cdots O_{x}U_{0}\left| \Psi \right\rangle$, where $\left\{ U_{i}\right\}$ is a set of unitary operators over $\mathcal {H}$ and $\left| \Psi \right\rangle$ is a fixed state in $\mathcal {H}$. The number of queries or steps is defined as the times that $O_{x}$ occurs in the algorithm.

Definition 1

An indexed set of pairwise orthogonal projectors $\left\{ P_{z}:z\in T\right\}$ is called a complete set of orthogonal projectors (CSOP) if it satisfies

$$\begin{aligned} \sum _{z\in T}P_{z}=I_{\mathcal {H}}, \end{aligned}$$

(1)

taking $I_{\mathcal {H}}$ as the identity operator for $\mathcal {H}$.

Given a CSOP defined for the algorithm, the probability of obtaining the output $z\in T$ is $\pi _{z}\left( x\right) =\left\| P_{z}\left| \Psi _{x}^{f}\right\rangle \right\| ^{2}$. We say that an algorithm computes a function $f:D\rightarrow T$ within error $\varepsilon$ if $\pi _{f\left( x\right) }\left( x\right) \ge 1-\varepsilon$ for all input $x\in D\subset \left\{ 0,1\right\} ^{n}$.

2.1 An alternative formulation for the QQM

In this section, we introduce notation from a previous work [18]. We define a product of unitary operators $\widetilde{U}_{n}=U_{n}U_{n-1}\ldots U_{0}$. We denote a CSOP $\left\{ \bar{P}_{k}:0\le k\le n\right\}$, where the range of each $\bar{P}_{i}$ is composed by vectors of the form $\left| i\right\rangle \left| \psi \right\rangle \in \mathcal {H}$, for $i\in \left\{ 0,1,..,n\right\}$ and any state $\left| \psi \right\rangle .$ We also introduce the notation ${\widetilde{P}_{i}^{j}=\widetilde{U}_{j}^{\dagger }\bar{P}_{i}\widetilde{U}_{j}}$. Notice that for any fixed j we have that $\left\{ \widetilde{P}_{k}^{j}:0\le k\le n\right\}$ is also a CSOP. The following definition introduces an alternative representation for quantum query algorithms on the QQM.

Definition 2

Consider a set $\mathbb {Z}_{n+1}=\left\{ 0,1,\ldots ,n\right\}$. An indexed set of vectors $\left\{ \left| \Psi \left( k\right) \right\rangle \right. \in \mathcal {H}:\left. k\in \mathbb {Z}_{n+1}^{t+1} \right\}$ is associated with a quantum query algorithm if we have that

$$\begin{aligned} \left| \Psi \left( a\right) \right\rangle =\widetilde{P}_{a_{t}}^{t}\ldots \widetilde{P}_{a_{1}}^{1}\widetilde{P}_{a_{0}}^{0}\left| \Psi \right\rangle , \end{aligned}$$

(2)

for all $a\in \mathbb {Z}_{n+1}^{t+1}$.

In Lemma 1, we show that vectors associated with some algorithm represent the final state as phase flips [18]. In Sect. 4, we analyze the relation between minimum norm (or cardinality) of such vectors, and the computational gap between classical and quantum query.

Lemma 1

If the indexed set of vectors $\left\{ \left| \Psi \left( k\right) \right\rangle \in H_{A}:k\in \mathbb {Z}_{n+1}^{t+1} \right\}$ is associated with a quantum algorithm then

$$\begin{aligned} \widetilde{U}_{t}^{\dagger }O_{x}U_{t} \ldots U_{1}O_{x}U_{0}\left| \Psi \right\rangle =\sum _{k_{t}=0}^{n} \ldots \sum _{k_{0}=0}^{n} (-1)^{\sum _{i=0}^{t}x_{k_{i}}}\left| \Psi \left( k_{0}, \ldots ,k_{t}\right) \right\rangle . \end{aligned}$$

(3)

Proof

Following Ref. [18], we give a proof by induction on t. For $t=0$, we have that Eq. (3) holds,

$$\begin{aligned} \widetilde{U}_0^\dagger O_x U_0 \left| {\Psi }\right\rangle= & {} U_0^\dagger O_x U_0 \left| { \Psi }\right\rangle \end{aligned}$$

(4)

$$\begin{aligned}= & {} \sum _{k_0 = 0}^n (-1)^{ x_{k_{0}} }\left| \Psi \left( k_{0}\right) \right\rangle . \end{aligned}$$

(5)

For the second part of the induction, we shall notice that the equation

$$\begin{aligned} O_{x}\left| \Psi \right\rangle =\sum _{i\in \left\{ k:x_{k}=0\right\} }\bar{P}_{i}\left| \Psi \right\rangle -\sum _{i\in \left\{ k:x_{k}=1\right\} }\bar{P}_{i}\left| \Psi \right\rangle \end{aligned}$$

(6)

implies the equation

$$\begin{aligned} \widetilde{U}_{j}^{\dagger }O_{x}\widetilde{U}_{j}\left| \Psi \right\rangle =\sum _{i\in \left\{ k:x_{k}=0\right\} }\widetilde{U}_{j}^{\dagger }\bar{P}_{i}\widetilde{U}_{j}\left| \Psi \right\rangle -\sum _{i\in \left\{ k:x_{k}=1\right\} }\widetilde{U}_{j}^{\dagger }\bar{P}_{i}\widetilde{U}_{j}\left| \Psi \right\rangle . \end{aligned}$$

(7)

Suppose that Eq. (3) holds for some t, then applying Eq. (7) we obtain

$$\begin{aligned}&\widetilde{U}_{t+1}^\dagger O_x U_t\ldots U_1 O_x U_0 \left| {\Psi }\right\rangle \\&\quad =\sum _{k_{t}=0}^{n} \ldots \sum _{k_{0}=0}^{n}(-1)^{\sum _{i=0}^{t} x_{k_{i}} } \sum _{k_{t+1}=0}^{n}(-1)^{x_{k_{t+1}}}\widetilde{P}_{k_{t+1}}^{t+1}\left| \Psi \left( k_{0},\ldots ,k_{t}\right) \right\rangle \\&\quad = \sum _{k_{t+1}=0}^{n} \ldots \sum _{k_{0}=0}^{n}(-1)^{\sum _{i=0}^{t+1} x_{k_{i}} }\widetilde{P}_{k_{t+1}}^{t+1}\left| \Psi \left( k_{0},\ldots ,k_{t}\right) \right\rangle \\&\quad = \sum _{k_{t+1}=0}^{n} \ldots \sum _{k_{0}=0}^{n}(-1)^{\sum _{i=0}^{t+1} x_{k_{i}} }\left| \Psi \left( k_{0},\ldots ,k_{t+1}\right) \right\rangle . \end{aligned}$$

$\square$

The previous theorem shows that a quantum state depends on several components whose phases change independently on input x. Notice that the phase $(-1)^{\sum _{i=0}^{t}x_{k_{i}}}$ of each component $\left| \Psi \left( k_{0}, \ldots ,k_{t}\right) \right\rangle$ is a Walsh function. Then, each of the components depends on t values from input, which at first sight is not impressive, considering that deterministic classical algorithms compute any function that depends on t values using t queries. However, all components together depend on the size n of input. Thus, we have the possibility of computing on n variables using just t queries, which gives us another intuition about the computational speed-up by quantum means. Therefore, this formulation presents quantum parallelism more explicitly than a sequence of unitary operators.

3 A classical simulation for quantum query algorithms and polynomials

In this section, we introduce our simulation of quantum query algorithms by classical algorithms. However, our simulation can also be extended to polynomials. This simulation is defined over the output probability $\pi _{z}\left( x\right)$ of the quantum algorithm.

We consider the Fourier basis for the vector space of all functions $f:\left\{ 0,1 \right\} ^{n}\rightarrow \mathbb {R}$ [15] given by the functions

$$\begin{aligned} \chi _{b}:\left\{ 0,1\right\} ^{n}\rightarrow \left\{ 1,-1\right\} , \end{aligned}$$

such that $\chi _{b}(x)=\left( -1 \right) ^{b\cdot x}$ for $b\in \left\{ 0,1 \right\} ^{n}$ and $b\cdot x=\sum _{i} b_{i}x_{i}$. This family contains a constant function that we denote as $\chi _{0}=1$. Therefore, any function $f:\left\{ 0,1 \right\} ^{n}\rightarrow \mathbb {R}$ can be represented as a linear combination

$$\begin{aligned} f=\underset{b\in \left\{ 0,1 \right\} ^{n}}{\sum }\alpha _{b}\chi _{b}, \end{aligned}$$

(8)

and we denote the Fourier 1-norm of f as

$$\begin{aligned} L\left( f\right) =\underset{b\in \left\{ 0,1 \right\} ^{n}}{\sum }\left| \alpha _{b}\right| . \end{aligned}$$

(9)

Another measure is the degree of f, which is defined as

$$\begin{aligned} \deg \left( f \right) =\max _{\left| b \right| } \left\{ b:\alpha _{b}\ne 0 \right\} , \end{aligned}$$

(10)

where |b| denotes the number of ones in b.

Fig. 1

The simulation produces a contracted version of the original output probability. The new output probability can be represented as a linear transformation applied over the original output probability

Figure 1 presents the intuition behind our simulation. At the right, we have $\pi _{1}\left( x\right)$, the probability of obtaining output 1 by a quantum query algorithm on input x. Such function is decomposed into a linear combination of functions $\chi _{b}$, following Eq. (8). The sub-simulations imply emulating each function $\chi _{b}$ by a classical algorithm that outputs 1 with probability $\widehat{\pi }_{1}^{b}\left( x\right) ,$ where: (1) $\chi _{b}(x)=1$ implies that $\widehat{\pi }_{1}^{b}\left( x\right) =1$; and, (2) $\chi _{b}(x)=-1$ implies that $\widehat{\pi }_{1}^{b}\left( x\right) =0$. Notice that each $\widehat{\pi }_{1}^{b}\left( x\right)$ is a probability and cannot have negative values as functions $\chi _{b}$. The composition step is assigning appropriate probabilities to each output $\widehat{\pi }_{1}^{b}\left( x\right) ,$ such that the sum produces an output probability whose shape resembles $\pi _{1}\left( x\right)$. As each $\widehat{\pi }_{1}^{b}\left( x\right)$ is similar but different in relation to $\chi _{b}$, this procedure accumulates an important error. The proof of the following theorem shows the details.

Theorem 1

Let $\mathcal {A}$ be a quantum algorithm that computes $f:S\rightarrow \left\{ 0,1\right\}$ for $S\subset \left\{ 0,1\right\} ^{n}$, within error $\varepsilon$ and t queries. Then, there is a classical algorithm which computes f within error

$$\begin{aligned} \tilde{\varepsilon }=\frac{\varepsilon +L\left( \pi _{1}\right) }{1+2L\left( \pi _{1}\right) } \end{aligned}$$

and 2t queries.

Proof

If a quantum algorithm applies t queries, then $\deg \left( \pi _{z} \right) \le 2t$ for every output z [10]. Let $\mathcal {D}\left( b\right)$ be the deterministic classic algorithm which outputs

$$\begin{aligned} \widehat{\pi }_{1}^{b}\left( x\right) =\frac{1}{2}+{{\,\mathrm{sgn}\,}}\left( \alpha _{b}\right) \left( \frac{\chi _{b}(x)}{2}\right) ,\end{aligned}$$

(11)

for input x, where ${{\,\mathrm{sgn}\,}}$ is the sign function and $|b| \le 2t$. We consider a randomized algorithm $\mathcal {R}$ which simply selects either: (1) an algorithm $\mathcal {D}\left( b\right)$, with probability $\frac{2\left| \alpha _{b}\right| }{1+2L\left( \pi _{1}\right) };$ or, (2) an algorithm that outputs 0 for any x, with probability $\frac{1}{1+2L\left( \pi _{1}\right) }$. Notice that algorithm $\mathcal {R}$ is the composition of sub-simulations, as we represent in Fig. 1. Since we denote by $\widehat{\pi }_{1}\left( x\right)$ the probability of obtaining output 1 given x with $\mathcal {R}$, by Eq. (11) we have

$$\begin{aligned} \widehat{\pi }_{1}\left( x\right)= & {} \frac{\underset{b}{\sum }2\left| \alpha _{b}\right| \widehat{\pi }_{1}^{b}\left( x\right) }{1+2L\left( \pi _{1}\right) }\end{aligned}$$

(12)

$$\begin{aligned}= & {} \frac{\underset{b}{\sum }\left| \alpha _{b}\right| +\underset{b}{\sum }\alpha _{b}\chi _{b}(x)}{1+2L\left( \pi _{1}\right) }. \end{aligned}$$

(13)

The algorithm $\mathcal {R}$ applies no more than 2t queries, since $\mathcal {D}\left( b\right)$ applies no more than 2t queries for each $|b| \le 2t$.

Now, we must prove an upper-bound for the error in the simulation. We divide such proof in two cases, when $f\left( x\right) =1$ and $f\left( x\right) =0$. If $f\left( x\right) =1$, then $\varepsilon \ge 1-\pi _{1}\left( x\right) =1-\underset{b}{\sum }\alpha _{b}\chi _{b}(x)$. This implies that

$$\begin{aligned} 1-\widehat{\pi }_{1}\left( x\right)= & {} 1-\frac{\left( L\left( \pi _{1}\right) +\underset{b}{\sum }\alpha _{b}\chi _{b}(x)\right) }{1+2L\left( \pi _{1}\right) }\end{aligned}$$

(14)

$$\begin{aligned}= & {} \frac{1+L\left( \pi _{1}\right) -\underset{b}{\sum }\alpha _{b}\chi _{b}(x)}{1+2L\left( \pi _{1}\right) }\end{aligned}$$

(15)

$$\begin{aligned}\le & {} \tilde{\varepsilon }. \end{aligned}$$

(16)

Analogously, if $f\left( x\right) =0$, then $\varepsilon \ge \pi _{1}\left( x\right) =\underset{b}{\sum }\alpha _{b}\chi _{b}(x)$ and this implies that

$$\begin{aligned} \widehat{\pi }_{1}\left( x\right) \le \frac{\varepsilon +L\left( \pi _{1}\right) }{1+2L\left( \pi _{1}\right) }=\tilde{\varepsilon }. \end{aligned}$$

(17)

$\square$

We described a classical simulation that imitates the output probability of a given quantum algorithm, but within a big error. Thus, the next theorem just gives a reduction in such error using probabilistic amplification.

Theorem 2

Let $\mathcal {A}$ be a quantum algorithm that computes $f:S\rightarrow \left\{ 0,1\right\}$ for $S\subset \left\{ 0,1\right\} ^{n}$, with error $\varepsilon$ and t queries. Then, there is a classical algorithm which computes f within error $\exp \left( {-\frac{j}{2\left( 1-\tilde{\varepsilon }\right) }\left( \frac{1}{2}-\tilde{\varepsilon }\right) ^{2}}\right)$, where $\tilde{\varepsilon }=\frac{\varepsilon +L\left( \pi _{1}\right) }{1+2L\left( \pi _{1}\right) }$ and using 2jt queries for $j\in \mathbb {N}$.

Proof

We use a corollary of Chernoff bound [8]. For $j,p,\beta$ such that $0\le p\le 1$, $0\le \beta \le 1$ and $0\le j$, we have

$$\begin{aligned} \sum _{i=0}^{m}\left( {\begin{array}{c}j\\ i\end{array}}\right) p^{i}\left( 1-p\right) ^{j-i}\le \exp {\left( -\beta ^{2}jp/2\right) }, \end{aligned}$$

(18)

where $m = \left\lfloor \left( 1-\beta \right) jp\right\rfloor$.

We define an algorithm $\mathcal {\widehat{R}}$ using the classical algorithm $\mathcal {R}$ within error $\tilde{\varepsilon }$ from Theorem 1. Algorithm $\mathcal {\widehat{R}}$ consists in applying probability amplification on $\mathcal {R}$, that is, executing algorithm $\mathcal {R}$ j times and then selecting the most frequent result. Define X as the random variable that represents the number of correct answers. Taking $\beta =1-\frac{1}{2\left( 1-\tilde{\varepsilon }\right) }$ and $p=\left( 1-\tilde{\varepsilon }\right)$ in Eq. (18), then the error in $\mathcal {\widehat{R}}$ is upper-bounded by

$$\begin{aligned} \mathbb {P}\left[ X\le \left\lfloor \frac{j}{2}\right\rfloor \right] \le \exp \left( {-\frac{j}{2\left( 1-\tilde{\varepsilon }\right) }\left( \frac{1}{2}-\tilde{\varepsilon }\right) ^{2}}\right) . \end{aligned}$$

(19)

$\square$

3.1 Polynomial simulation

The same technique can be applied for simulating a polynomial $p\left( x\right)$ approximating a function, instead of simulating the output probabilities of a given quantum algorithm. In this sense, Theorems 1 and 2 can be generalized. In order to formulate the corresponding theorems, we consider the usual notion of polynomial approximation:

Definition 3

A polynomial $p:\mathbb {R}^n\rightarrow \mathbb {R}$ $\varepsilon$-approximates a function $f:S\rightarrow \left\{ 0,1\right\}$ for $S\subset \left\{ 0,1\right\} ^{n}$, if $\left| p\left( x \right) -f\left( x \right) \right| \le \varepsilon$ for all $x \in \left\{ 0,1 \right\} ^n$.

Theorem 3

Let $p:\mathbb {R}^n\rightarrow \mathbb {R}$ be a polynomial that $\varepsilon$-approximates $f:S\rightarrow \left\{ 0,1\right\}$ for $S\subset \left\{ 0,1\right\} ^{n}$. If p has a degree equal or less than 2t, then there is a classical algorithm which computes f within error

$$\begin{aligned} \tilde{\varepsilon }=\frac{\varepsilon +L\left( p\right) }{1+2L\left( p\right) } \end{aligned}$$

and 2t queries.

Proof

The proof is similar to the proof of Theorem 1.$\square$

We similarly introduce the corresponding reduction error theorem.

Theorem 4

Let p be a polynomial that $\varepsilon$-approximates $f:S\rightarrow \left\{ 0,1\right\}$ for $S\subset \left\{ 0,1\right\} ^{n}$. If p has a degree equal or less than 2t, then there is a classical algorithm which computes f within error $\exp \left( {-\frac{j}{2\left( 1-\tilde{\varepsilon }\right) }\left( \frac{1}{2}-\tilde{\varepsilon }\right) ^{2}}\right)$, where $\tilde{\varepsilon }=\frac{\varepsilon +L\left( p\right) }{1+2L\left( p\right) }$ and using 2jt queries for $j\in \mathbb {N}$.

Proof

The proof is similar to the proof of Theorem 2, but reducing error in Theorem 3 instead Theorem 1. $\square$

4 Upper-bounds for quantum speed-up

In this section, we describe conditions which can slow down our simulation. Quantum speed-up only occurs when no classical simulation is efficient enough, thus any condition that makes difficult any classical simulation is a necessary condition for this computational gain. In this sense, we measure the quantum speed-up for a given quantum algorithm by the quotient $\frac{R}{t}$, where (1) such quantum algorithm applies t queries, and (2) an optimal classical algorithm executes the same computational task in R queries. This quotient can be interpreted as how much faster is a quantum algorithm in relation to the best classical algorithm.

The following theorem, which upper-bounds quantum speed-up using Fourier 1-norm, is the core of our results. It basically shows how high values for Fourier 1-norm are related to the speed quotient that we denoted.

Theorem 5

Consider $D\subset \left\{ 0,1\right\} ^{n}$ and a function $f:D\rightarrow \left\{ 0,1\right\}$ that is computed within error $\varepsilon >0$ and t queries, by a quantum query algorithm. If we define

$$\begin{aligned} F_{\varepsilon }\left( l\right) =\left\lceil \frac{-16\ln \left( \varepsilon \right) \left( 1+l\right) \left( 1+l-\varepsilon \right) }{\left( 1-2\varepsilon \right) ^{2}}\right\rceil , \end{aligned}$$

(20)

then

$$\begin{aligned} \frac{R_{\varepsilon }\left( f\right) }{t}\le F_{\varepsilon }\left( L\left( \pi _{1}\right) \right) , \end{aligned}$$

(21)

where (1) $R_{\varepsilon }\left( f\right)$ denotes the minimum number of queries that are necessary for computing f within error $\varepsilon$ by a randomized decision tree (See [12] for a detailed definition.) and (2) $\pi _{1}(x)$ is the probability of the quantum algorithm returning output 1 for a given input x.

Proof

Suppose that we simulate the quantum algorithm using the randomized algorithm of Theorem 2 and promising an error that does not exceed $\varepsilon$ for f. Thereby, from Eq. (19), we have

$$\begin{aligned} \varepsilon = \exp \left( -\frac{j}{2\left( 1-\tilde{\varepsilon }\right) }\left( \frac{1}{2}-\tilde{\varepsilon }\right) ^{2} \right) . \end{aligned}$$

(22)

As $\frac{R_{\varepsilon }\left( f\right) }{t}\le \left\lceil 2j\right\rceil$, if we obtain j from Eq. (22) we have Eq. (21).$\square$

Last theorem has consequences in exact quantum complexity, as we find in the following corollary.

Corollary 1

Consider a total function $f:D\rightarrow \left\{ 0,1\right\}$, then

$$\begin{aligned} \frac{R_{\varepsilon }\left( f\right) }{Q_{E}\left( f\right) }\le F_{\varepsilon }\left( L\left( f\right) \right) , \end{aligned}$$

(23)

where $Q_{E}\left( f\right)$ denotes the number of queries applied by an exact quantum query algorithm computing f.

Proof

If a quantum query algorithm is exact, optimal and computes a total function then $t=Q_{E}\left( f\right)$ and $\pi _{1}=f$.$\square$

Theorem 5 can also be formulated for approximate polynomials, as follows.

Theorem 6

Consider $D\subset \left\{ 0,1\right\} ^{n}$ and a function $f:D\rightarrow \left\{ 0,1\right\}$ that is $\varepsilon$-approximated by a polynomial $p:\mathbb {R}^n\rightarrow \mathbb {R}$. If $\deg \left( p\right) \le 2t,$ then

$$\begin{aligned} \frac{R_{\varepsilon }\left( f\right) }{2t}\le F_{\varepsilon }\left( L\left( p\right) \right) . \end{aligned}$$

(24)

Proof

Similar proof as for Theorem 5, but applying Theorem 4.$\square$

We may expect from Fourier 1-norm that low values must imply problems that are easily simulated by classical means. Theorem 5 guarantees that low values of the Fourier 1-norm in relation to t imply such efficient classical simulation. Notice that Fourier 1-norm is defined on the output probability. Then, an explicit expression for the Fourier 1-norm as a function of the algorithm itself may be useful. Let k, h be vectors in $\mathbb {Z}^{t}_{n+1}$ and $|b|\le 2t$. We denote $\left( k,h\right) \sim b$, if

$$\begin{aligned} (-1)^{\underset{i}{\sum }x_{k_{i}}+\underset{i}{\sum }x_{h_{i}}}=\chi _{b}(x). \end{aligned}$$

Thus, for a t-query algorithm, we have the expression

$$\begin{aligned} L\left( \pi _{1}\right) =\underset{|b|\le 2t}{\sum }\left| \underset{\begin{array}{c} \left( k,h\right) \sim b \end{array}}{\sum }\left\langle \Psi \left( k\right) \right| P_{1}\left| \Psi \left( h\right) \right\rangle \right| , \end{aligned}$$

(25)

by applying Lemma 1. Considering that each pair $\left( k,h\right)$ is related to a unique b, we can obtain the following upper-bound for $L\left( \pi _{1}\right)$,

$$\begin{aligned} \widetilde{L}\left( \pi _{1}\right) =\underset{k}{\sum }\underset{h}{\sum }\left| \left\langle \Psi \left( k\right) \right| P_{1}\left| \Psi \left( h\right) \right\rangle \right| . \end{aligned}$$

(26)

These expressions are based on the state decomposition given by Definition 2. Lemma 1 implies that each quantum algorithm has its own state decomposition, thus next theorem relates metrics on such set of vectors with the gap between quantum and classical query.

Theorem 7

Using the same hypothesis of Theorem 5, denoting $\#S$ as the cardinality of set S and defining $d=\#\left\{ k:\left| \Psi \left( k\right) \right\rangle \ne 0\right\}$, we have

$$\begin{aligned} \frac{R_{\varepsilon }\left( f\right) }{t}\le & {} F_{\varepsilon }\left( \widetilde{L}\left( \pi _{1}\right) \right) , \end{aligned}$$

(27)

$$\begin{aligned} \frac{R_{\varepsilon }\left( f\right) }{t}\le & {} F_{\varepsilon }\left( \left( \underset{k}{\sum }\left\| \left| \Psi \left( k\right) \right\rangle \right\| \right) ^{2}\right) , \end{aligned}$$

(28)

$$\begin{aligned} \frac{R_{\varepsilon }\left( f\right) }{t}\le & {} F_{\varepsilon }\left( d\right) , \end{aligned}$$

(29)

and

$$\begin{aligned} \frac{R_{\varepsilon }\left( f\right) }{t}\le F_{\varepsilon }\left( \frac{1}{\underset{k}{\min }\,\left\langle \Psi \left( k\right) \right| \left. \Psi \left( k\right) \right\rangle }\right) . \end{aligned}$$

(30)

Proof

As $F_{\varepsilon }$ is an increasing function, Eq. (27) follows directly from Eq. (26) and Theorem 5. Equation (28) is also derived from Eq. (26) by observing that

$$\begin{aligned} \left| \left\langle \Psi \left( k\right) \right| P_{z}\left| \Psi \left( h\right) \right\rangle \right| \le \left\| \left| \Psi \left( k\right) \right\rangle \right\| \left\| \left| \Psi \left( h\right) \right\rangle \right\| , \end{aligned}$$

(31)

which gives

$$\begin{aligned} L\left( \pi _{1}\right) \le \left( \underset{k}{\sum }\left\| \left| \Psi \left( k\right) \right\rangle \right\| \right) ^{2}. \end{aligned}$$

(32)

Applying Lemma 1, we obtain

$$\begin{aligned} \left\langle \Psi \right| \left. \Psi \right\rangle =\underset{k,h}{\sum }\left\langle \Psi \left( k\right) \right| \left. \Psi \left( h\right) \right\rangle =1. \end{aligned}$$

(33)

Then, using it with $\underset{k}{\sum }\left\| \left| \Psi \left( k\right) \right\rangle \right\| \le \sqrt{d}\underset{k}{\sum }\left\langle \Psi \left( k\right) \right| \left. \Psi \left( k\right) \right\rangle$ and Eq. (32), we have

$$\begin{aligned} L\left( \pi _{1}\right) \le d. \end{aligned}$$

(34)

Finally, Eq. (30) follows from $d\left( \underset{k}{\min }\,\left\langle \Psi \left( k\right) \right| \left. \Psi \left( k\right) \right\rangle \right) \le 1.$ $\square$

5 Alternative applications

Our results from Sect. 4 have a main theoretical motivation, which is showing the relation between quantum speed-up and quantum parallelism. Furthermore, the theorems are interesting for related subjects that we discuss below.

5.1 Upper-bounds for randomized complexity

Theorems 5 and 6 may be applied for finding upper-bounds on $R_{\varepsilon }$. For example, consider Deutsch–Jozsa algorithm, thereby we have the output probability

$$\begin{aligned} \pi _{1}\left( x\right) =\frac{1}{n^{2}}\left( n-2\left| x\right| \right) ^{2} \end{aligned}$$

for inputs of size n. We obtain the terms $\left\{ \alpha _{b}\right\}$ by applying the pairwise orthogonality between functions $\chi _{b}$. The algorithm works by applying just one query. Thus, from the fact that $\deg \left( \pi _{1}\left( x \right) \right) \le 2$ [10], we have that if $|b|>2$ then $\alpha _{b}=0$. This leaves us with three cases to analyze. First, if $|b|=0$, then $\alpha _{b}=\frac{1}{n}$, notice that there is just one index b satisfying $|b|=0$. Second, if $|b|=1$, then $\alpha _{b}=0$. Third, there are $\frac{n\left( n-1\right) }{2}$ indices b such that $|b|=2$, in this case $\alpha _{b}=\frac{2}{n^{2}}$. Therefore, we have that $\sum \left| \alpha _{b}\right| =1$, which implies

$$\begin{aligned} R_{\varepsilon }\le \left\lceil \frac{-16\ln \left( \varepsilon \right) \left( 2-\varepsilon \right) }{\left( 1-2\varepsilon \right) ^{2}}\right\rceil \end{aligned}$$

by Eq. (21). This is not quite tight numerically because a classical decision tree applies 2 queries in order to solve Deutsch–Jozsa problem within error $\frac{1}{3}$. However, this is asymptotically tight and proves that Deutsch–Jozsa algorithm can be simulated classically using a constant number of queries and fixed error.

5.2 Lower-bounds for exact quantum complexity

Corollary 1 can be applied for finding lower-bounds on $Q_{E}$. For example, consider the total function $AND_n:\big \{0,1\big \}^{n}\rightarrow \{0,1\big \}$ where $AND_n\left( x\right) =1$ if and only if $x_{i}=1$ for all i. We denote weight of input x as the number of ones in x. A randomized decision tree computing $AND_n$ must discriminate the input with weight n from the set of inputs with weight $n-1$. Suppose that some randomized decision tree computes $AND_n$ with less than $\frac{n}{3}$ queries, then such randomized tree is a probabilistic distribution over a set of deterministic decision trees querying less than $\frac{n}{3}$ values in x. Then, in order to discriminate an input of weight n from the set of inputs with weight $n-1$, the randomized tree will find 0 for some $x_i$ with expectation less than $\frac{1}{3}$. In this sense, $R_{\frac{1}{3}}\left( AND_n\right) \ge \frac{n}{3}-1$.

Considering that $L\left( AND_n\right) =1$, we have $Q_{E}\left( AND_n\right) \in \Omega \left( n \right)$ by Eq. (23), which is asymptotically tight [7].

5.3 Polynomial approximation by quantum algorithms

There is an equivalence between 1-query algorithms and degree-2 polynomials. That is, a partial Boolean function f can be approximated by a polynomial for some error bounded by $\varepsilon > \frac{1}{2}$ if and only if f can be computed by a quantum algorithm with error bounded by $\varepsilon ' > \frac{1}{2}$ and a single query. However, the problem of transforming polynomials of higher degree to quantum algorithms still needs more results [4]. Theorem 3 implies that t-query algorithms compute any function approximated by degree-t polynomials with Fourier 1-norm bounded by a constant. Then, the high degree problem is reduced to find algorithms for polynomials with a high Fourier 1-norm.

6 Conclusion

In the present work, we identified a necessary property for a hard classical simulation of quantum query algorithms, namely a high Fourier 1-norm defined over the output probability. A remarkable feature about Fourier 1-norm is that it depends on both evolution and measurement steps. Properties like quantum entanglement are defined just on the quantum states, which implies that a poor measurement step can cancel advantages obtained in the evolution stage, where we assume that such evolution stage was hard to simulate. Nevertheless, the accuracy of Fourier 1-norm for approximating quantum gain depends on a simulation, whose relation with the most efficient classical simulation is unknown.

We also formalized the advantage given by quantum algorithms, as the quotient between the classical and quantum complexities for a given task. We have that such quotient is upper-bounded by an expression which depends quadratically on the Fourier 1-norm. Thus, a large factor produced between quantum and classical algorithms implies a large Fourier 1-norm. Our result suggests the following intuitions:

• 1. Output probabilities with large Fourier 1-norms imply that such output probability can be represented by a function whose shape is much different from any function in the Fourier basis—functions that can be efficiently simulated by classical means.

• 2. Output probabilities with high Fourier 1-norms imply that many functions from Fourier basis are acting simultaneously. This strongly suggests quantum parallelism.

We can also link Fourier 1-norm to quantum parallelism as follows. A quantum query algorithm can be viewed as a state decomposition by Lemma 1, which is denoted as a set of vectors associated to the algorithm. This formulation emphasizes the presence of quantum parallelism, because each combination of vectors in the decomposition represents a function in the Fourier basis, where such functions are added producing an output probability function. The Fourier 1-norm is related to this decomposition. Since a high Fourier 1-norm implies: (a) a big number of nonzero vectors in such decomposition, i.e., high values for $\#\left\{ k:\left| \Psi \left( k\right) \right\rangle \ne 0\right\}$; and, (b) minimum product values that are not too big for such vectors, i.e., low values for $\left( \underset{k}{\min }\,\left\langle \Psi \left( k\right) \right| \left. \Psi \left( k\right) \right\rangle \right)$; then (a) and (b) are also necessary conditions for a hard classical simulation. Both measures can be linked to quantum parallelism by the following intuition. If $\#\left\{ k:\left| \Psi \left( k\right) \right\rangle \ne 0\right\}$ is low, then there are less combinations of vectors adding functions on the output probability function. Larger values for $\underset{k}{\min }\,\left\langle \Psi \left( k\right) \right| \left. \Psi \left( k\right) \right\rangle$ imply lower values for $\#\left\{ k:\left| \Psi \left( k\right) \right\rangle \ne 0\right\}$. However, it also implies that the output probability function has a shape closer to functions in the Fourier basis, hence such output probability has a cheap classical simulation. The intuition behind is that Fourier 1-norm is a measure for quantum parallelism and gives a quadratic upper-bound to the potential quantum speed-up.

Finally, the present work leaves the following open problems:

• An additional motivation for studying the Fourier 1-norm is that it is a parameter that we may control. Finding degree-2 polynomials is an alternative strategy for obtaining 1-query quantum algorithms [4]. Thus, developing a method for obtaining high 1-norm polynomials of degree 2 and bounded in $\left\{ 0,1\right\} ^{n}$ would help to find algorithms offering a potential advantage over classical algorithms.

• A high Fourier 1-norm implies a necessary condition for quantum query speed-up. Can we obtain a necessary and sufficient condition by adding another property?