# 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`$