Quantum Computing For Computer Scientists

Quantum computing is coming, so a lot of people are trying to articulate why we want it and how it works. Most of the explanations are either hardcore physics talking about spin and entanglement, or very breezy and handwaving which can be useful to get a little understanding but isn’t useful for applying the technology. Microsoft Research has a video that attempts to hit that spot in the middle — practical information for people who currently work with traditional computers. You can see the video below.

The video starts with basics you’d get from most videos talking about vector representation and operations. You have to get through about 17 minutes of that sort of thing until you get into qubits. If you glaze over on math, listen to the “index array” explanations [Andrew] gives after the math and you’ll be happier.

Billing the Deutsch Oracle as an example of why quantum computing is superior makes us nervous. The premise is you can identify a black box in one operation as opposed to two in a classical computer. The problem is that to do that, you need to modify the black box to take an extra bit. Well, if I can modify the black box to take an extra bit (in a different way) with a classical computer, I can identify the function in one operation, also. However, it is a good explanation of a fundamental concept — it just doesn’t bear scrutiny that it demonstrates the advantage of quantum.

It might be better, in our opinion, to show how it mirrors parallelism in classical computing. For example, if I can modify my black box to do the same operation on two bits in parallel, I get the same result. The quantum modification — granted — is simpler, but it still required you to add an extra bit and modify the black box.

The video closes with some live demos using the Microsoft tools. If you watch this video and want to do some hands-on in your browser — or even a real machine — you might enjoy our tutorial series. If you are trying to just explain or understand quantum computing at a higher level, the IBM videos are a lot more breezy.

16 thoughts on “Quantum Computing For Computer Scientists

  1. i worry quantum computers are never going to fulfill the promises that they’ve been hyping for so long. honestly there’s no proof we can push the quantum noise levels down far enough to make a cost efficient machine. this isn’t just a engineering problem its a running into the limits of the universe problem so it my not be something we can really fix.

    it will be interesting one way or the other but i do wander whats it going to be like when the bubble bursts and the reality is all that’s left.

    1. Considering how much progress they have made in the last 5 years the “we will have qc in 5 years” quote that have been re-stated again and again in the last 20? Years might soon become true..

      Its a bit early still to throw in the towel.

  2. QC seems to have always been badly explained, maybe because the explanations focused on how it worked rather than what it does. I like to think of its capabilities in terms of pattern matching or search. I am no expert on QC but it seems that what it allows is to find multiple patterns in data in a single pass. This clearly could make searching data, Fourier analysis and breaking crypto codes much faster. It doesn’t seem to do much to help with executing logic algorithms. Existing computers do that quite well. QC should make the pattern identification part of AI easier but maybe not the decision making part, so It will probably need a hybrid of the two.

    As an aside on the “Microsoft trying to monopolize QC” comment, that is not special to MS. It is inherent in how unrestrained capitalism works. The steel and rails barons did it, IBM did it before MS and Apple, Google, Amazon, Facebook etc are doing it now. Competition is good for consumers but bad for making a lot of money.

  3. Correct me if I’m wrong, but I just read an article stating that some Princeton students discovered the use of synthetic diamonds to be a key to avoiding collapse so it may happen sooner than we think. Either way, it’s interesting to see the universe unfold before our very eyes. The future is bright.

    1. The problem with the research you are referencing is that they still have to cool the diamond down to extremely low temperatures which is very expensive. In addition, qubits as color centers in diamond work optically which add many other sources of noise in storage and read out.
      What color center qubits are really good for is entanglement distribution (https://arxiv.org/abs/1712.07567). We will probably see these systems used in quantum repeater networks for entanglement first. Using color centers for a quantum computer would require a LOT of things to go right including noise reduction and competing qubit technologies significantly under performing.

  4. Al, regarding your objection: “Well, if I can modify the black box to take an extra bit (in a different way) with a classical computer, I can identify the function in one operation, also.”

    I understand where the intuition is coming from, but that extra bit doesn’t matter. It helps to understand what we mean when we say some computer is more powerful than another: it means the more-powerful computer uses fewer resources (time, memory, circuit depth, etc.) to calculate the same function. We state resource usage using Big O notation, where constant factors are disregarded (so O(2*n^2 + 3) is the same as O(n^2), for example). In this specific case, the resource we are measuring is something called “query complexity” – basically the number of times some black-box function must be invoked to solve a problem.

    One important fact you’re missing here is that reversible classical computers are exactly as powerful as non-reversible classical computers. Sure we need to add some extra scratch bits to the reversible computers so we don’t erase information, but that all comes out in the Big O wash. So when we add another bit to our black box to make it reversible, we don’t add any additional computational power.

    The question is thus “is a quantum computer more powerful than a reversible classical computer, when measuring query complexity?” which by transitivity becomes “is a quantum computer more powerful than a classical computer, when measuring query complexity?” to which the Deutsch Oracle problem answers “yes”.

    If none of that convinced you, then this will: consider the generalized Deutsch Oracle problem, called the Deutsch-Josza problem. Instead of a function on a single bit, the black box takes in N bits. The question we want to answer is whether the black box maps all 2^N possible input values to the same output (is constant) or maps half the 2^N possible input values to 0 and the other half to 1 (is balanced). On a classical computer, you would need to query the black box 2^N/2 times before you can determine the answer, but on a quantum computer you still need only a single query. Furthermore – and this is part relevant to your objection – you only need N+1 qbits (N input qbits and 1 output qbit) in your rewired reversible black box. There’s no way you could use that single additional qbit to speed up your computation in a meaningful way no matter how you rewired the black box.

Leave a Reply to hackadaveCancel reply

Please be kind and respectful to help make the comments section excellent. (Comment Policy)

This site uses Akismet to reduce spam. Learn how your comment data is processed.