New answers tagged

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