I understand the basic of quantum computing (qubits, superposition, probability distributions, noise, how observing works, etc), but I’m struggling to understand what operations actually go on within an algorithm. I know you essentially do linear algebra to transform a vector closer and closer to the “true” outcome, but that’s very abstract. What’s actually going on when one does that? How does an operation “know” what the “true” outcome is?
Apologies if my terminology is way off—I’m only just looking into this, lol.
The gates of a digital quantum computer are basically equivalent to the transistor gates of a regular CPU. Here is a list. The two notable ones are the controlled NOT gate (which is the equivalent of a 2-bit XOR gate) and the Hadamard gate (which is a useful unary permutation of a single quantum bit). Using these two gates you can construct any quantum circuit, just like NAND can make any computer. The challenge is to physically build these gates in a way where quantum bits can pass through them without interacting with them or the rest of the machinery (which would destroy their superposition). There are some other gates too, which, though equivalent to a combination of the above, may be easier to physically build or represent longer circuits condensed into a single operation.
Any digital quantum algorithm can be built using these gates. You are right that the individual operations do not know what the true outcome is, they just perform theirs CNOTs and whatever. You cannot move closer to the true outcome bit by bit. Instead you have to use clever algorithms to combine all the outcomes together in such a way that all the outcomes you do not want destructively interfere. This is only possible (in a way that is provably superior to polynomial classical computation) for a select number of known quantum algorithms, such as Shor’s algorithm, and generally for the BQP complexity class. Notably, quantum algorithms provably CANNOT solve NP-complete problems (unless P=NP that is). There is no way to arrange for destructive interference in the general case. So the algorithms only work for almost-but-not-quite-officially-NP-complete problems like integer factorization and quantum physics simulations.
There could be more useful NP-but-not-NP-complete problems out there that can be solved by a BQP algorithm, but for which we haven’t found the algorithm yet! That’s the allure of theoretical quantum computing. Then there is the practical engineering challenge of building these gates and chaining them into circuits. Finally there is analog quantum computing, which is what many currently-realized quantum computers essentially are, but I don’t know much about them. I think as a computational complexity class they are equivalent to BQP of digital computers.