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.

INSERTED to show the fundamental operation of Grover’s algorithm. Suppose there is a search problem. The possible answers are 0, 1, 2, and 3, but the right answer is 2. So the quantum computer is put in a superposition of all four states, and it goes through a sequence of steps to see which one is correct, and inverts its amplitude, like the black dots and arrows below:

You can see that arrow 2 has been inverted inside the machine, but there’s no way to tell that outside, because only probabilities are visible outside, which are amplitudes squared, and when squared they are all equal.

However, the amplitudes have a mean, indicated by the red line, and the computer can be made to go through a sequence of steps that inverts each amplitude about the mean.
When that is done, the amplitudes, and the probabilities, transfer to state 2, the right answer !
So if the machine is observed, state 2 shines forth.

It’s not quite this simple. Generally it takes multiple cycles of the machine, forward and backward, inverting at the end of each cycle, to maximize the probability of the right answer. Also, one must take care not to do it any more than that number of times, because it can just as easily reverse itself.

So why do they say quantum computers are so fast?
Because every time you double the number of qubits, you square the parallelism, but you don’t square the length of time, so eventually it wins.

Isn’t that fun?

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.

What would a C like language look like if it was designed for qubits? Would types change?

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.

In order to make the most effective possible use of a quantum computer, one needs to be able to deal with inputs and outputs that are states of a quantum register, for which there is really no classical analogue. Speaking from some years of experience in the field of quantum information, I must warn you that no one really has a good intuition for this beyond the abstract mathematics of C* algebras, and I’m told that even this intuition turns out to be inadequate if you start wondering about relativity theory.

The class of problems that are efficiently solvable on a quantum computer is known as BQP, for Bounded Quantum Polynomial. This is the quantum version of BPP, and you can find more information in this paper: http://www.scottaaronson.com/papers/bqpph.pdf

I was told just last night by a quantum algorithms researcher that there is a very important problem that is BQP-complete: solving a linear system of N equations. Classically, this is solvable in O(N) steps with Gaussian elimination. The Harrow-Hassidim-Lloyd algorithm (http://arxiv.org/abs/0811.3171) solves it in polylog(N), provided you are willing to accept an answer that has the solution encoded as a quantum state. If you want to make full use of a quantum computer, it therefore seems necessary for you to have a type corresponding to the state of a quantum register.

Though I am a little outside of my particular expertise right now, I would hazard a guess that you would be able to program a quantum computer as long as you had access to a type corresponding to magic states. That’s a difficult concept, though, that requires quite some study of the subject.

Be warned that we are a very long time from having a quantum programming language, because we are at a very primitive stage of quantum computing research. Asking for a quantum C right now would be like going to Alan Turing and asking him to design Python. We haven’t even got the quantum version of the vacuum tube yet!