4.3 KiB
4.3 KiB
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}`
- where
- 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`
- we start with the input
- 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`
- measuring the last of these bits gives us
- 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
- 1 if there is a
- 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}`
- function
- 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 could use a curve fitting algorithm if
- 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`
- i.e. if