I would like to add some more references to Scott's comment: Indeed, Clebsch-Gordan transforms (that you can think of as multi-register quantum Fourier transforms) are a useful tool in the design of ...

There is at least one example that I can remember, but there are probably more that I am not aware of. Recently, Maarten Van den Nest and Wolfgang Dürr found a new classical algorithm (arXiv:1304....

To solve this problem there is a fast deterministic algorithm based on Smith normal forms whose worst-case complexity is upper-bounded by the cost of matrix-multiplication over the integers modulo $m$....

If by "classically using the solutions of the linear equation" you mean "accessing the information in the exactly same way a classical computer does" or, in other words, "obtaining the classical ...

For sure, the automata performs a measurement after reading each symbol "a" and applying an associated unitary $V_a$. Yet, it is not really meaningful to compute the amplitudes of the state to be ...

A Simple Proof that Toffoli and Hadamard are Quantum Universal, D. Aharonov summarising a result found by Yaoyun Shi. Because it is a simple, well written, 4 pages paper which makes you think and ...

This classical post-processing exploits several non-trivial group theoretical properties of Abelian groups. I wrote a didactic explanation of how this classical algorithm works here [1]; other good ...

After some time, I managed to find a perhaps not-optimal but simple algorithm that proves that the complexity of the problem is polynomial. Algorithm (a) Compute a generating-set of the ...

It seems that this problem in full-generality is though. These two references might be helpful to you. Here [1] the pure-state discrimination of MUBs is studied in a cryptographic set-up. The ...

Correct me if I am wrong, but it seems to me that you are interested in the class BQP/qpoly. Definition from Complexity Zoo: "The class of problems solvable by a BQP machine that receives a quantum ...

It is important that, in the definition you provide, the matrix lives in a finite field, say $\mathbb{Z}_m$ where $m$ is prime. This allows you to use Euler's theorem to compute the double-...

There are clasical algorithms [1], [2], [3] to compute the determinant of a $k\times k$ matrix using $O(k^\omega)$ floating-point operations, where $O(k^\omega)$ is the number of operations that you ...

The archive of recorded seminars of the Perimeter Institute is both useful and entertaining. The Qubit Lab is a Youtube channel that explains advanced topics on quantum information and computation ...

Visioning is both dangerous and polemic in this field, so we should be cautious with this topic. Yet some Q-algorithms with polynomial speed-ups have interesting potential applications. It is known ...

In addition to the previous answers, there is a package that computes Fourier transforms for solvable non-commutative groups based on this algorithm. The software has a tool to decompose Fourier ...