Quantum computation contains a lot of concepts foreign to most computer scientists. Like ‘dark matter’, black holes and the like, this ignorance has a tendency to breed wild speculation, and set up some very unrealistic expectations. I’m going to take a stab here at explaining a few of these concepts in a digestible way, and try to add some healthy skepticism along the way.

On a classical computer, operations may be performed on some user input, and a result is produced derived from that input. “add 2 and 2” produces 4. It is natural to assume the user does not know the output of an algorithm before it is executed, or else why do it at all. Let us say such an algorithm performs “computational work”. It’s a very natural assumption. A quantum computer may also perform simple logical and arithmetic operations such as these, albeit much more expensively, slowly, and more troublesome to set up. For those kind of operations, you’re really better off using your fingers. However, a number of quantum algorithms, designed specifically to be faster than their classical counterparts, do not seem to perform computational work when they are considered in their entirety, including the construction of the quantum circuit. I found this very disturbing.

For example, Deutsch’s Algorithm, and it’s more general successor, the Deutsch-Jozsa(DJ) algorithm are canonical demonstrations of the advantage of quantum computing. For those unfamiliar, the problem it is solving is this:

You are given a function that takes as its input an n-bit integer, and returns either a zero or a one. Consider every possible input to this function. If it returns a zero for every case, or a one for every case, then let us say this function is ‘constant’. If it returns zero for exactly half of the cases, and one for the other half, then let us say this function is ‘balanced’. The function is also constrained to be only either constant or balanced! The problem is then to determine whether the given function is constant or balanced.

So, for a given function, there are 2^n possible inputs to try. A classical algorithm would only need to run that function on one more than half of these inputs to solve the probem. So that makes this algorithm O(2^(n-1)). The DJ algorithm on the other hand claims to solve this problem in constant time! The discovery of that much speedup for any problem, even a toy problem such as this one is pretty unprecedented, and could very well imply some sort of massive paradigm shift in the way we do computing. This claim interested me enough to dig in and really try to understand what going on under the hood. The devil is really in the details here though. It takes a lot of time and effort to learn the mathematics necessary to to understand any quantum algorithm, and even then, it’s easy to wind up chasing your tail. I would not claim to be an expert by any stretch, but I feel I’ve explored this algorithm enough to rough in the details for a layman, and get into this little issue that seems to be a disappointing theme with quite a few of these algorithms claiming a ‘quantum advantage’.

The DJ algorithm is not long, wikipedia gives a pretty thorough explaination. The basic procedure is this: Start by putting each qubit in a superposition such that the probability of measuring a one is exactly 50%. Likewise for zero. The probability density of these qubits and any qubit for that matter, oddly have the mechanics of a wave. Quantum gates are really just ways of manipulating these probability density waves relative to each other, usually by just changing their phase. The goal here is to increase the probability of measuring the correct answer as much as possible by paring down the space of possible answers using interference. Also, qubits may interfere with each other. This is because all or many qubits in a quantum computer are entangled, and basically act like one big composite probability density wave. This is exactly what the DJ algorithm does. The result is, if the input function is constant 0 or 1, the DJ output will be 1 100% of the time ideally. If the input function is balanced, the output is zero 100% of the time ideally. It really is a very clever algorithm, and would seem to run in constant time. That is, until you try to start implementing things and ask, “So how do you program it?”, and in particular “How do you input a function into this program?” Haha.

So to ‘program’ a ‘quantum computer’, you really just design a combinatorial-like circuit to solve the problem you want to solve, much like an FPGA. For a user to get data into the circuit, the answer is basically the same, you must hard-wire that data in. There is no I/O! For complicated input like a function, this hard-wiring process can be very challenging, math-heavy, and implementation specific. Making that implementation scalable is another big problem. The biggest issue though is much more fundamental. Have you noticed yet? We have to design a circuit for a function that we somehow don’t know is constant or balanced to determine whether it is constant or balanced. And, you might remember, we have to also constrain this function to be constant or balanced, without even knowing what it is?! Congratulations, you’ve just discovered a ‘quantum oracle’, the cornerstone of quantum computing pop-science hype.

Oracles are not inherently evil, and have been used since nearly the dawn of computing to great effect in complexity and the design of algorithms in academia. You have a component of an algorithm you don’t know how to implement, so you add a black box called an oracle in its place, and judge complexity assuming that black box has constant complexity. But if you were like me and were looking for a simple algorithm to understand what the big stink about quantum computing is, you probably went cross-eyed reading Shore’s algorithm and its numerous implementations, and settled on Deutsch’s algorithm and friends. It’s the first algorithm described in Nielson and Chuang, and it’s what inspired Shore’s algorithm. So I don’t think I am unreasonable in feeling a little mislead by the claims made about the DJ algorithm. Here’s the abstract to the original paper:

A class of problems is described which can be solved more efficiently by quantum computation than by any classical or stochastic method. The quantum computation solves the problem with certainty in exponentially less time than any classical deterministic computation.

What a headline! This paper has been cited 2595 times as of this writing. And yet the algorithm really doesn’t do anything without that oracle function. Deutsch and Jozsa go on in that paper to state explicitly that they are using an oracle, but I think it’s fair to say that headline is simply not true of the Deutsch-Jozsa algorithm. And I would go further to question whether oracles have a place in quantum computing at all. There is no I/O! Your quantum algorithm cannot call another function in the middle of its execution, all that has to be hard-coded into the circuit. But perhaps I’ll expound on that in a later post…

Claims about the potential of quantum computing are running rampant. Buzzwords like ‘quantum supremacy/superiority’, and Nevan’s Law are everywhere, touted by serious companies the likes of Google and IBM. Their marketing departments certainly take most of the blame for this hype-train, but academics also need to take care to communicate clearly, and start taking into account how their words are being interpreted and misinterpreted. That’s the point right, to communicate, not to just fund a waste of time? And all that hype pulls impressionable young people into this field, without the information they need to make an informed decision.

Science is so important, and I think Quantum Computing is certainly worth our attention. We study, and we learn that things we thought were possible are not. But as some doors close, others open. We’re answering questions, it’s all good. That’s how science works. These algorithms are not by themselves wrong or deceiptful, but they are posed in ways that allow them to be easily misinterpreted. Simply pointing out that as it stands, the DJ algorithm and its friends perform no computational work could perhaps be useful to people trying to make a tangible contribution to the field.