Quantum computer is basically: prepare initial state, perform some specific unitary evolution and finally extract some information by performing measurements.

We can imagine the first step as preparing all states to be zero: |0>.

The unitary evolution is usually constructed (in physical approaches it is a bit more complicated...) by "quantum gates": which in opposite to classical ones, have to be reversible.

For example (f is any classical gate): (x,y,z)->(x,y,z XOR f(x,y) )

These gates/unitarity require large number of auxiliary variables - set initially to 0 and ignored after all.

The unitary evolution should be made of a fixed net of such quantum gates - calculation goes exactly once through each of them. I haven't met with loops there as you would like - they seem impossible in this approach and doesn't seem required.

Here is schematic picture of probably the only really practical (known?) quantum algorithm: newbielink:http://en.wikipedia.org/wiki/Shor%27s_algorithm

[nonactive] to find nontrivial factor of large number (N):

So after state preparation, in QC there are usually used Hadamar gates to make superposition of all possible inputs. Then you make some classical calculation on these all possible inputs (not using loops).

Then there is the step containing real superiority of quantum calculations: selection of only those possibilities having the same value of the classical calculations. In Shor case: of all 'a' such that 'y^a mod N' is the same (y is freely chosen). These 'a's fulfilling the condition form a periodic set and its period allows to find a nontrivial factor of N - the QuantumFourierTransform is to extract the period.

Observe that these gates are also reversible classically - so shouldn't we be able to reverse the calculations classically?

For example find 'a' giving chosen value of 'y^a mod N', what would also allow to easily find nontrivial factors? ... or solve 3SAT: fix 'true' on the end of verifier and propagate back to finally get some variables leading to this 'true' (much stronger use, unavailable for standard quantum computers).

Unfortunately there is essential problem with that: the large number of auxiliary variables for classical calculations - we don't know values they should have.

The superiority of quantum computers is that they can simultaneously initialize variables in the past and enforce the same value in the future by measurements while selection (unknown/random value - if we could control it, we would get muuuch stronger computers).