Advances in quantum computing: presentation by Dr. Brian La Cour

Dr. Brian La Cour from University of Texas at Austin gave a presentation on the latest state of quantum computing to Austin's Quantum Computing meetup in March of 2017. Here are some prominent points from it.

Several big companies are getting into quantum computing now: Google, Microsoft, IBM. There are significant differences between their approaches.

Google plans to solve a problem with 49 qubits, a problem that would demonstrate quantum supremacy (getting a clear speedup with a quantum algorithm over a classical algorithm), but is completely useless in real life. The problem with that is that when you progress to the quantum supremacy frontier, you can no longer check the answer with a regular device. Or it would take a very long time. So Google's argument will probably be based on asymptotic trend, with how they are doing with more qubits. But overall this problem of how to check the results will be more difficult in the future.

Brian La Cour talks about Google's race to quantum supremacy at the Austin Quantum Computing meetup

We are a long way from solving Shor's algorithm and breaking internet's encryption. But quantum simulation is a near term application. It goes back to Richard Feynman's discussions of quantum computing. We can simulate things on a digital computer, but it's not very efficient. When you want to add another spin, another atom, you have to double the memory. What better thing to simulate a quantum system than a quantum system?

There is a difference between gate-based quantum computing (like what IBM and partially Google does) and quantum annealing, like what D-Wave does, and partially Google.

Gate-based device (that operates on gates, similar to classical gates) is a universal quantum computer. D-Wave's computer is specialized, it is only useful for certain optimization problems. And so far those problems have been pretty contrived, not necessarily corresponding to anything in real life. Even so there is no definitive evidence that the D-Wave's computer is advantageous for solving specific practical problems, as compared to classical solvers. There is a professor somewhere who, every time when D-Wave claimed that their quantum computer was solving some problems more efficiently, took it as a challenge to find a classical algorithm that would beat it. And so far he has been successful. But lately this has become less clear, because he has been, in Brian's words "exploiting what he knows about the problem". (Mathematicians and computer scientists can make it sound like it's a bad thing. But perhaps he means that while the professor is exploiting special knowledge about a problem, the quantum annealing computer can't make use of that knowledge, thus he is not comparing apples to apples? -- E.)

IARPA -- funding agency for intelligence community, analogy of DARPA -- is focused on developing next-generation quantum annealing, a universal quantum annealer. Their goal is, can you take benchmark projects and scale them to the thousands of qubits that D-Wave has?

Microsoft is looking at high-level languages for quantum computing. They are designing high-level languages that optimize what low-level languages do. They also do their own research into topological quantum computing, which is a very different approach than the qubit-based QC, but Brian thinks that's technologically so far away it's probably never going to happen.

This brings us to another Brian La Cour point, which is that now is a good time even for ordinary software developers to get involved in quantum computing, and you don't have to be a researcher to do it. There are people who are building interfaces in conventional programming languages to QASM, IBM's Quantum assembly language. This is where you as an individual can make a contribution: figure out how to do things in QASM and implement an interface to it in your favorite language. Also, individuals can play around with the IBM's Quantum Experience, a web interface to the IBM's quantum computer, and familiarity with it could put you in a position to get a job at some company that does quantum computing (not that there are many of those currently -- E.).

According to Brian, quantum gamification is also a trend. However, he used the word "gamification" not the way it is typically used (to incentivize certain user behaviors by making them seem like a game). He meant it more literally in the sense of games that teach you something about quantum mechanics. In some of those games people perform actions that help quantum researchers. Here are some examples:

• www.scienceathome.org
• qCraft -- a "mod" to the popular Minecraft game. It uses "quantum blocks" to teach superposition, observation, and entanglement.
• There are even games that have been programmed on IBM Quantum Experience, such as Quantum Battleship.
• Decodoku was developed to help researchers with quantum error correction. You are protecting researchers from errors.
• cat-paper-scissors game (I could not find it by googling -- E.)
• Quantum Cats from University of Waterloo, Canada. It's like angry birds, except cats can be in superpositions.

Brian La Cour noted that not only quantum computing research is strong in Canada, Canadian QC scientists also do a lot of educational outreach. US scientists don't do nearly as much, but they should.

As always, the least predictable part of any presentation is the audience's questions, and Brian got a few of those.

Audience member. Have you heard of neuromorphic computing?

Brian replied that he has heard about it, but that there wasn't any connection there to quantum computing. It was just another unconventional way to compute. Apropos of unconventional computing, quantum computing in a way is a throwback to analog computing: encoding information in continuous variables, except what comes out is still digital.

Audience member. Can quantum computing be used to mine bitcoins?

Aside from currently existing quantum computers being nowhere near powerful enough to mine bitcoins, Brian also noted that the value of bitcoin is based on the fact that bitcoins are computationally difficult to find. So if you find an algorithm to mine them fast and reliably, it will devalue them.

Audience member. How big a leap is it to go from classical programming to quantum programming? Is it a totally different beast?

Brian. It is a totally different beast. If you try to do things like conditionals and loops, you are doing it wrong. Instead of conditionals you have control gates, where value of one qubit controls what happens to another qubit. Which is sort of like conditional, but linear. A qubit in a superposition of 0/1 controls another qubit which is also in superposition.

The way you think about quantum computing is taking your entire data space, or state space, and think about it all at once.

You initialize all to 0 and apply Hadamard gates all at once. It puts them in superposition of all possible states, and then you do operation on them. You are looking at the whole haystack and apply operations to the whole haystack until you find a needle. You don't examine each value and look whether it's a needle.

"Computer Chess" movie: come for the 80s tech nostalgia, stay for the weirdness

The movie "Computer Chess" passed largely unnoticed in the big theaters (it didn't even play in Austin), but I greatly enjoyed this mockumentary about a computer chess tournament in the early 1980s. At first I didn't think that it would have much value beyond nostalgic or historical. A nostalgia trip for those who were computer nerds in the eighties, I thought it might be educational for someone like me, who never saw a PC up close until the early 90s. It must have been harder to be passionate about computing in the days when computers didn't fit in your pocket; the really devoted computer scientists, such as the ones portrayed in this movie, put their machines on dollies and wheeled them from room to room when they wanted to play them against one another.

But what drew me in for historical value made me stay for the character study.

At first, the players seem pretty ordinary college students as they get together in a hotel room in the evening and "debate" big questions, such as plausibility of artificial intelligence, or the nature of consciousness, with all the banality of a young person discovering those questions for the first time and not yet having done their intellectual homework. But as the tournament progresses and their programs start to go astray, their personalities blossom into bouquets of quirks.

The movie juxtaposes the players with an "officially" weird group of people: the attendees of a wacky couples retreat that goes on in the hotel the same weekend. Barking at each other like dogs is just one of the ways the New Age'y couples attain some kind of transcendence and deepen their connection. Ostensibly, the computer chess tournament and the retreat could not be more different, but soon they become more similar than one could guess. As it turns out, smart people who are deeply absorbed in, even obsessed with their work, quickly veer into outlandish beliefs. A tired, overwhelmed, razor-focused-on-one-thing human mind is unwilling to accept natural explanations when things don't go the way it wants. The movie does not ridicule anyone: human weirdnesses are portrayed in a loving, non-judgmental manner. It merely observes as the two polar opposites -- computer geniuses and New Age'y quacks -- move closer together. It's fitting that the final match between a human chess master and the computer takes place side-by-side with the woo-woo practice in an accidentally double-booked conference room.

Speaking of conference rooms: this movie has a feel of the lowest-budget-movie-ever. It takes place entirely in a nondescript Ramada Inn. Who would have thought that you could shoot a movie in Austin, and not even have Austin cityscape anywhere in the backdrop? On behalf of my adopted city I might be a little offended. :-)

Of programmatic thinking in low-tech situations

These days it's been fashionable to insist that everybody should learn to program. Some argue it's the next kind of literacy (a federal judge who learned how to code could correctly estimate how long it would take to implement a certain function), others say the importance of programming in an ordinary person's life is overblown. There is a vast difference between basic programming knowledge and being a professional software developer. The question is, can this basic literacy have applications in everyday life? Can it improve the life of a non-programmer? I liked this article that demonstrates how knowing how to program benefits even the people who are not programmers. When you have developed a mentality that lets you see many life problems from an engineering perspective, you see how software could help you improve even those life processes that you previously didn't think a computer could solve. It's a matter of thinking algorithmically, of seeing what could be automated. I have a similar problem as the one described in the article. I take lots of pictures of people at conventions and conferences, and there isn't a good way to "connect" photos of strangers with their names (which I forget instantly). However, unlike the casting directors in the article, I have neither assistants with spreadsheets, nor do people parade in front of me one by one like models. I also think that it would be awkward to ask them, after introducing myself, to write their names on a piece of paper, and to pose with it. :-) The best I can do is take pictures of their name tags, but sometimes those are missing, or flipped over to the blank side, or flash bounces off of them in a way that makes them illegible. On the other hand, my tablet allows me to add notes to any picture I take. (Well, I can't add notes to a picture directly, but I can save it to Evernote with a note attached.) So perhaps I'll just have to take two pictures of everyone -- one with the real camera, for quality, and the other with the tablet, for documentation. If a situation is not structured, there isn't much room for a programmatic solution to a problem.

Pipelined motherhood

Not long ago a friend, referring to my second child (who just turned 1), asked me how my second round of motherhood was treating me. He tried to use a computer metaphor for it, so he put it as "how is serial motherhood going?" Then he immediately admitted that this metaphor was inaccurate. It's not really serial, because I'm raising two children, not one at a time. You could say it's parallel, but that doesn't convey the idea of going from one child to two. So, pausing for a bit, he decided it could be called pipelined motherhood. Since I haven't heard about pipelined architecture, which (as a very oversimplified explanation) lets computers run tasks in parallel by starting them at different times, I thought about it in UNIX pipe terms. So I asked: "Do you think I feed one child the output of the other?"

Sometimes a problem pounces upon your brain...

Sometimes a mathematics / computer science problem pounces upon your brain, and takes possession of it for half the day -- at least until you figure out that its general case does have a solution. Then you finally escape its clutches, feeling that you haven't accomplished much; but you've brushed off some dust of that old math/CS knowledge that sometimes gets asked at software development job interviews. So it's not all a waste.

The problem was posted on Facebook by a friend who encountered it in his engineering work.

Suppose you have tasks A, B, and C. Task A occurs n_A times in a given time period, task B occurs n_B times, and task C occurs n_C times. Let's say n_A is 7, n_B is 2, and n_C is 1. The time between any two tasks is the same. Let's call it a unit time interval. These tasks repeat endlessly in a loop. The problem is to arrange the tasks in such a way that the number of time intervals between any two tasks of the same type will be minimized.

It may seem simple, but... it's not.

Ideally, any two A-tasks will be separated by at most ceil((nA + nB + nC) / nA) intervals, any two B-tasks are separated by at most ceil((nA + nB + nC) / nB), and any two C-tasks are separated by at most ceil((nA + nB + nC) / nC) intervals, where ceil() is ceiling, a function that rounds up a number to the nearest integer larger than it.

I came up with an example (or a counterexample, if you will) where it is impossible to find a schedule that satisfies those constraints.

Say task A occurs 19 times in a given time period, task B 13 times, and task C 3 times. Then nA + nB + nC = 35. ceil(35/19) = 2, so A-tasks should be separated by no more than 2 intervals. B-tasks need to be no more than ceil(35/13) = 3 intervals apart. Now, if you put a C-task between two A-tasks, then B-constraint will be violated. Any segment A-A is surrounded by B's, i.e. it will be a subset of B-A-A-B, and those two B's are 3 intervals apart. Put a C in the middle, and B-tasks will be 4 intervals apart. That's greater than ceil(35/13) = 3. If you put a C between A and B-tasks, then A-constraint will be violated, because you'll have a sequence A-C-B, so an A following that sequence will be 3 intervals away from the first A. That's greater than ceil(35/19) = 2.

Of course, there are many combinations of frequencies for which it IS possible to find an optimal schedule, for example 19-11-5. Also, if the numbers are multiples of other numbers, this problem may have additional properties that may make it solvable. Then again, engineers usually don't care about exact solutions, rather than "good enough" approximate solutions. If you require that the number of intervals between two tasks of the same type exceed the optimal only a certain percentage of times, the problem becomes complex enough to be a fodder for master's thesis. I wouldn't be surprised if it has been already solved in the academic literature. I just don't know of a good enough way to search for papers or theses that may have been published on this topic.

Further thoughts: you could map this problem to a graph theory problem. Each task can be a node in a graph, and you would need to find a shortest route for visiting all the nodes -- "shortest" as determined by the costs required to visit each node. This would be the traveling salesman problem, which is NP-complete. But this proves nothing, because this particular problem might map to a special instance of traveling salesman problem that's solvable in polynomial time.