How is programming a quantum algorithm different? What would a C like language look like if it was designed for qubits? Would types change?
When I looked into this some time ago, it was clear that quantum algorithms, while not particularly fast, permit exponentially massive parallelism. So they will shine in cases involving search in spaces that are not practical with sequential hardware, even massively parallel sequential hardware.
One property of quantum algorithms is that they have to be reversible. Any given algorithm can be translated into one that is reversible, by adding to it enough record-keeping to allow it to be run backward.
Another property is that getting an answer out of a quantum algorithm is a hit-and-miss affair, because what you get at the end of a computation is multiple answers, each with its own probability. It needs to be run in such a way that the answer you want has high probability. This may involve running the algorithm forward and backward multiple times.
Check out Grover's Search Algorithm.
I was personally interested in how this could be applied to verification of software correctness. Now we test software by throwing a bunch of test inputs at it and (to be overly simple) seeing if it hits an Assert. In a quantum computer it might be possible to run it in parallel against a much denser set of inputs and see if any of those cases hit an Assert.
Like if the input to the algorithm were 128 bytes, or 1024 bits, there are 2^1024 or 10^308 possible different inputs. There is no way to test that many inputs on a conventional computer, but a quantum computer could try them all in parallel.
It would be so drastically different as to be incomprehensible as C.
The main issue (as I understand it) is that quantum computing does not work in a nice imperative manner 'do this, then that, then this other thing'. Trying to force C's ability to do that into the 'processor' of quantum computer will be if not impossible, wildly inefficient.
Programming algorithms for quantum computers (again, as I understand them) tend to be closer to functional programming style map/reduce, since quantum computing allows all of the candidates in the 'reduce' part to exist concurrently and "fall out" of the computer when observed.
Note that there are some existing algorithms for quantum computers, even though the devices don't exist to run them. Simon's algorithm for example.