quantum mechanics - Shor's algorithm - its causality and similar exploitation of QM?

Shor's algorithm is rather the most interesting quantum algorithm as it shifts a problem which is believed to need exponential classical time, to polynomial time for quantum computer, additionally endangering asymmetric encryption like RSA and ECC.

The real question is if there are other problems, beside factorization and similar discrete logarithm problem, which can be shifted from exponential to polynomial time thanks to quantum computers? Are there known such other examples?

It is generally clear that to design a quantum algorithm, we should start with Hadamar gates, perform some unitary evolution, then measurement. However, personally for me the unitary part is a bit too abstract for direct algorithmic thinking - Shor grasps what seems to be a general and powerful mechanism, which might be possible to exploit also for essentially different problems.

So I am looking for quantum algorithms exploiting QM in a similar way as Shor - here is a diagram for its quantum subroutine (source):

1. The Hadamar gates create superposition of all (exponential number) values for input qubits.


2. Then we perform a classical function on them, which is here: "f(a) = y^a mod N", where N is the number we would like to factorize, y is some (usually random) number smaller than N.


3. Then we perform measurement of value of this function f(a)=m, which is random, but this measurement restricts the original ensemble to only input values a, such that f(a)=m.


4. Mathematics says that this restricted ensemble has to be periodic, this period can be concluded from value of (quantum) Fourier transform, and allows to conclude the factors.

What is surprising is the causality here (marked in the diagram) - the consequence of restricting the ensemble seems to propagate back in time to calculation of the function?

Finally the general approach (we might try to exploit for different problems) is:

1. use Hadamar gates to get superposition of all inputs,


2. perform some classical function f,



3. measure value of this function m, restricting the original ensemble to f(a)=m,


4. extract some information from the final restricted ensemble.

This possibility of restring ensemble to a fixed value of a chosen function seems powerful, but trying to use it for various NP-complete problems, I couldn't get any valuable help from it - the main obstruction is that the measured value of f is random.

Beside periodicity with QFT, what other information could we extract from such restricted ensemble? Asking if its size is larger than one is simple - any other questions we can perform?

Any thoughts? Interesting quantum algorithms beside Deutsch, Grover and Shor?