Introduction to models of quantum computation and quantum programming languages

Miszczak has put together a paper, Introduction to models of quantum computation and quantum programming languages. Skimming through it, it seems to be a good overview of the subject and a quicker read than some other texts at 40 pages. While not a complete overview of quantum programming techniques, still worth flipping through. The abstract:

The goal of this report is to provide an introduction to the basic computational models used in quantum information theory. We various review models of quantum Turing machine, quantum circuits and quantum random access machine (QRAM) along with their classical counterparts. We also provide an introduction to quantum programming languages, which are developed using the QRAM model. We review the syntax of several existing quantum programming languages and discuss their features and limitations.

Quantum Information Processing with Adversarial Devices

I just came across this on arXiv: Quantum Information Processing with Adversarial Devices. This is a thesis by Matthew McKague out of the University of Waterloo.

I only skimmed the first part of it so far, but seems like some interesting work. Most quantum programming methods proposed make use of Knill's QRAM model, either explicitly or implicitly. Knill's QRAM model essentially states that a quantum computer is a slave device controlled by a classical computer. Given this, I've always pondered the possibility that something could get in between and tweak the input or output of the quantum computer. So along those lines, interesting to see this.

An Overview of Quantum Computing for Technology Managers

I came across this paper on arXiv: An Overview of Quantum Computing for Technology Managers by Eleanor G. Rieffel. It provides a good overview of nearly all aspects of quantum computing. Unfortunately the one area missing was quantum computer programming. It is great to have algorithms and physical implementations, but we still need a way to write code to carry those algorithms out. The closest was the coverage of quantum circuit diagrams. If it were to be expanded in the future to cover quantum computer programming, I would imagine that Knill's QRAM model [1] would play a big part since it is used (sometimes implicitly) in many programming proposals.

This paper is also part of Wiley's Handbook of Technology Management.

References
[1] E. Knill, "Conventions for Quantum Pseudocode," Los Alamos National Laboratory LAUR-96-2724, 1996.

Article on Implementing Quantum Computers

I came across this article: Quantum computers are coming- just don't ask when. I'm no expert on physical implementations of quantum computers, but I thought it gave a good overview of some of the current physical implementations and challenges. The optimistic view of overcoming the challenges for building and quantum computers is right on target in my opinion.

I also thought that the end of the article was particularly noteworthy: it mentions that the first quantum computers may be devices that are originally used as subsystems of classical computers. This is Knill's QRAM model as I've previously written about. It is good to see that the software and hardware worlds of quantum computing are thinking along the same lines for initial implementations. There is a lot of work still to be done, but we're making good progress.

More Thoughts on Quantum Computers Becoming a Reality

I wrote a few weeks ago in a previous post about William Halal [1] and when we'll have quantum computers. To summarize: the best guess he's gathered from consulting a bunch of experts is 2021 plus or minus 5 years- which seems reasonable to me.

Current computers where an expensive resource when we first had them. It took decades until they were cheap and practical enough where you could have one at home. I think the same will be true with quantum computers, they'll be very expensive at first. For this reason I see them being a shared resource at first. In other words it will be something that multiple classical computers share. That sharing could be at the institution level, such as a university having some available much like early computers. It also isn't unreasonable to think that processing time could be rented out on it, much like Amazon's EC2.

One obvious question is how the classical computers will interact with the quantum computer. Nearly all proposals for programming quantum computers explicitly or implicitly make use of Knill's QRAM model [2]. In Knill's QRAM model the classical computer is the master and the quantum computer is the slave:

Things get a little more complicated when you throw in multiple classical computers for a single quantum resource. Each of them cannot have full control of the quantum resource and have it function correctly. However, Knill's QRAM model can be expanded to include a "quantum controller" between the classical computer(s) and quantum resource:
This has the advantage that all the logic to deal with the clients can be built into the quantum controller. The controller could also talk to the clients through a standardized protocol, meaning that different physical implementations of quantum computers could still be utilized through the same interface. The controller could also do some other things:

• Queue up requests for operations from a client and execute them at once.
  
• On the fly optimization?
• Deal with disconnected clients at any stage in the computation.
  

The list goes on. Obviously the implementation of this is hard. How exactly do the controller and classical computers communicate for instance? A lot of work would have to go into this, which is why I've listed it as an area for future research in my dissertation. Like programming quantum computers, I think we're best off tackling this issue before quantum computers become a reality outside the lab. Doing so will allow us to hit the ground running with quantum computers instead of stumbling along like we did in the early days of classical computing.

References
[1] W. E. Halal, Technology's Promise: Expert Knowledge on the Transformation of Business and Society, 1 ed. New York, NY: Palgrave Macmillan, 2008.
[2] E. Knill, "Conventions for Quantum Pseudocode," Los Alamos National Laboratory LAUR-96-2724, 1996.