New answers tagged phase-estimation
2
I don't think the last step holds. For example, choose $A$ to be the permutation matrix
$$A=\begin{pmatrix}0&0&1\\1&0&0\\0&1&0\end{pmatrix},$$ which indeed satisfies $A^3=\mathbb{I}$. Mathematica can perform both of the following:
$$A^{1/n}=\left(
\begin{array}{ccc}
\frac{1}{3} \left(2 \cos \left(\frac{2 \pi }{3 n}\right)+1\right) &...
3
I think the algorithm class you are referring to is EQP (Exact Quantum Polynomial-Time).
There is a famous breakthrough paper by Ambainis that shows for a superlinear advantage between exact quantum algorithms over their classical counterparts (classical deterministic algorithms) for the query complexity of a total Boolean function. Later Ambainis, Iraids ...
Top 50 recent answers are included