Polynomial Method

• [[quantum-computing]]
• method for determining computational complexity(?)
• if we have an oracle $\mathsf{O}_x$ that sends $\ket{i}\ket{b}$ to $\ket{i}\ket{b \oplus x_i}$
  • where $x_i \in \left\{0,1\right\}$ for $i \in \left[N\right]$
  • then $\alpha\ket{i}\ket{0} + \beta\ket{i}\ket{1}$ maps to $\left(\beta x_i + \alpha\left(1 - x_i\right)\right)\ket{i}\ket{0} + \left(\alpha x_i + \beta\left(1 - x_i\right)\right)\ket{i}\ket{1}$
  • so where $\alpha_{i,b}$ is a polynomial with degree at most $k$, we end up with a polynomial $\alpha'_{i,b}$ with degree at most $k + 1$, when we map a sum $\sum_{i,b} \alpha_{i,b} \ket{i}\ket{b}$ through the oracle to $\sum_{i,b} \alpha'_{i,b} \ket{i}\ket{b}$
• the method assumes the oracle $\mathsf{O}_x$ and a family of unitary operators $\mathcal{U}_i$ where $i \in \left[T\right]$ that do not query $x$
  • we start with the input $\ket{0}\ket{0}$, then $\alpha_{i,b} = 0$ everywhere except one index where $= 1$, i.e. a degree 0 polynomial
  • we apply $\mathcal{U}_0$, then $\mathsf{O}_x$, then $\mathcal{U}_1$, etc.
  • because $\mathcal{U}_i$ does not query $x$, we end up with a resultant state whose amplitude polynomial is at most degree $T$
• add some ancilla bits to the algorithm ($\ket{z}$) that can be served to $\mathcal{U}$ (but obviously don't matter to $\mathsf{O}$)
  • measuring the last of these bits gives us $\operatorname{Prob}\left[z_{last} = 0\right] = \sum_{z_{last = 0}} \left|\alpha_{i,b,z}\right|^2$
  • when you square a polynomial, the degree doubles
  • the probability of any output then is a polynomial of a degree at most $2T$
• example
  • function $\operatorname{OR}\left(\vec{x}\right) =$ 1 if there's at least one $1$ in $\vec{x}$, $0$ otherwise
  • if we have a quantum alg $\mathcal{A}$ that outputs the correct answer with certainty
  • this means that the probability of the answer being $1$ is
    • 1 if there is a $1$ in $\vec{x}$
    • 0 otherwise
  • the polynomial that represents this is $1 - \left(1 - x_0\right)\left(1 - x_1\right)\cdots$, which has a degree of $N$
  • if $N \leq 2T$ then our number of queries $T \geq \frac{N}{2}$
• for algorithms with bounded error ([[grovers-algorithm]], [[quantum-phase-estimation]], [[quantum-counting-algorithm]]), the polynomial describing our algorithm can be non-one
  • i.e. if $f\left(\vec{x}\right) = 1$, then $\frac{2}{3} \leq p\left(\vec{x}\right) \leq 1$
  • in this case $f$ is the search oracle and $p$ is our polynomial
  • we say $p : \mathbb{R}^n \to \mathbb{R}$ "approximates" $f : \left\{0,1\right\}^n \to \left\{0,1\right\}$ if $\left|p\left(\vec{x}\right) - f\left(\vec{x}\right)\right| \leq \frac{1}{3}$
  • $\widetilde{\operatorname{deg}}_{\frac{1}{3}}\left(f\right)$ is defined as the lowest degree of all polynomials that approximate $f$
    • $\tilde{P}_{\textsf{And}}\left(x_1, x_2\right) = \frac{1}{3}\left(x_1 + x_2\right)$
    • $\tilde{P}_{\textsf{Or}}\left(x_1, x_2\right) = \frac{2}{3}\left(x_1 + x_2\right)$
  • if we show that the approximating degree of $\textsf{Or}$ is $\sqrt{N}$, we prove that Grover's Algorithm is optimal
    • we could use a curve fitting algorithm if $\textsf{Or}$ was univariate
    • $\textsf{Or}$ is just a function on the [[hamming-weight]]: the order of bits does not matter
    • so any multivariate polynomial that approximates $\textsf{Or}$ can have terms such as $x_i x_j$ replaced with $\frac{1}{n \choose 2} \left(x_1 x_2 + x_1 x_3 + \cdots + x_{n-1} x_n\right)$
    • this transformation is $\operatorname{sym}$, producing a symmetrized polynomial, and this transformation will never increase the degree, but may reduce it
      • for any polynomial approximation that only depends on Hamming weight, the symmetrization is also an approximation
  • we can produce a curve to fit the points $\left\{\left(0, 0\right), \left(1, 1\right), \left(2, 1\right), \ldots, \left(n, 1\right)\right\}$, where each point can have an error of at most $\frac{1}{3}$
    • notably, we don't care where the polynomial hits outside of these x-values (integral points)
    • this curve cannot have a degree less than $\sqrt{n}$ due to the number of times it crosses the x-axis
  • we can do the same for parity to show you have $\widetilde{\operatorname{deg}}\left(\operatorname{parity}\right) = n$