Matt Purkeypile on Quantum Computer Programming

D-Wave Python Dev Kit

2012-01-17T20:41:00.000-08:00

Looks like D-Wave has a developer kit setup for Python, as outlined in this tutorial on their site: http://www.dwavesys.com/en/dev-tutorial-finance.html. Looks like they realized the same thing I did: to really be applicable for the commercial environment quantum computers need to be programmed via frameworks and not new quantum specific languages.

When I started work on Cove I actually started doing the implementation in both Python and C#. I quickly realized that was creating a lot of unnecessary work for myself and quickly abandoned the Python implementation. My reason for settling on C# was largely that the libraries could be used by multiple languages. However, I still think Python is a great candidate- Python's readability and simple learning curve make it a natural choice.

Quantum chip out of Bristol

2011-12-12T20:18:00.000-08:00

They've made some recent progress at Bristol University, making a small quantum chip. Some articles:

TechEye
Crazy Engineers
ZME Science
And of course, the Bristol press release.

Q & A with Seth Lloyd

2011-11-15T20:50:00.001-08:00

Here's a short question and answer with Seth Lloyd of MIT in Popular Science. As one would expect, this is more of a primer being in PopSci.

Caltech awarded funding for quantum research

2011-10-25T21:11:00.000-07:00

Caltech awarded $12.6 million for new Institute for Quantum Information and Matter.

More progress

2011-10-25T21:07:00.001-07:00

More progress, from the National Science Foundation: Tiny crystal towers enlighten understanding of photon emission, could inspire diamond microchips for quantum computing. (Image from the release.)

Maintaining Entanglement for an Hour

2011-08-27T09:22:00.000-07:00

Maintaining quantum states for any length of time is one of the big challenges in quantum computing. So this news about maintaining entanglement for an hour is encouraging. (Image from the article.)

Suppressing decoherence

2011-07-25T19:40:00.000-07:00

Some progress towards suppressing decoherence, a major stumbling block towards physical implementations of quantum computers.

Dave Bacon Moves to Google

2011-07-16T08:53:00.001-07:00

I came across this: Dave Bacon, previously at the University of Washington, has moved on to Google. Is the commercialization of quantum computing on the horizon?

Michael Nielsen on Open Science

2011-07-16T08:47:00.000-07:00

Michael Nielsen of [1] fame on open science:

[1] Nielsen, Michael A., and Isaac L. Chuang. Quantum Computation and Quantum Information. 2008. 1 ed. Cambridge, UK: Cambridge University Press, 2000. 8.

Quantum computing named one of the hottest 10 fields in science

2011-06-28T19:56:00.001-07:00

The Financial Times has named quantum computing one of the 10 hottest fields in science in a recent article.

Paper: Verification of Quantum Programs

2011-06-22T19:44:00.000-07:00

I'm of the opinion that formal verification of programs has a limited set of applications, in large part due to the "good enough" software principle. Nonetheless, it is nice to see work in the quantum programming area. Here's a just posted paper on arXiv: Verification of Quantum Programs by Ying, Yu, Feng, and Duan.

QIS-XML: An Extensible Markup Language for Quantum Information Science

2011-06-19T10:16:00.000-07:00

By Pascal Heus out of George Mason University: QIS-XML: An Extensible Markup Language for Quantum Information Science.

Cooling through computation

2011-06-06T20:48:00.000-07:00

Erasing data generates heat. For example, an And gate can erase data because if you get a false (0) you don't know if the inputs were both false or if just one of them were 0. Hence quantum computers need to perform reversible operations. Here is some pretty cool work on cooling computers by the computations they perform.

D-Wave sells quantum computer to Lockheed Martin

2011-06-01T20:19:00.000-07:00

For those who have not seen it yet, D-Wave has sold its first quantum computer to Lockheed Martin for 10 million. Here are a few of the many articles about it:

Verdal on the cover of the new Scientific American

2011-05-18T20:45:00.001-07:00

Vlatko Verdal, of [1] fame, wrote an article titled "Living in a Quantum World", which made the cover of this month's (June 2011) cover of Scientific American.

References
[1] Vedral, Vlatko. Introduction to Quantum Information Science. 1 ed. Oxford, Great Britain: Oxford University Press, 2006.

More D-Wave Claims

2011-05-18T20:24:00.001-07:00

For those who have not seen it yet, D-Wave is making some new claims. I've been skeptical since 2007, and still feel the same way. I think Scott Aaronson described the situation well in his blog, as he usually does about D-Wave.

Information sharing at the quantum limit

2011-05-02T19:55:00.000-07:00

Out of the Max Planck Institute yesterday: Information sharing at the quantum limit (A photon transfers its secrets onto a single atom).

UC Santa Barbara to get $7.5 million for quantum computing

2011-05-02T19:49:00.000-07:00

UC Santa Barbara is getting $7.5 million for quantum computing research from the Defense Department. The work will be lead by Awschalom.

Quantum Public Key Encryption

2011-03-24T19:48:00.000-07:00

One of the most cited benefits of a quantum computer is that it can factor, therefore breaking many current public key encryption systems. That makes this recent paper by Kawachi, Koshiba, Nishimura, and Yamakami certainly interesting: a quantum version of public key encryption. Here's a brief article in MIT Technology Review, and the paper on arXiv. The abstract:

We introduce a computational problem of distinguishing between two specific quantum states as a new cryptographic problem to design a quantum cryptographic scheme that is "secure" against any polynomial-time quantum adversary. Our problem, QSCDff, is to distinguish between two types of random coset states with a hidden permutation over the symmetric group of finite degree. This naturally generalizes the commonly-used distinction problem between two probability distributions in computational cryptography. As our major contribution, we show that QSCDff has three properties of cryptographic interest: (i) QSCDff has a trapdoor; (ii) the average-case hardness of QSCDff coincides with its worst-case hardness; and (iii) QSCDff is computationally at least as hard as the graph automorphism problem in the worst case. These cryptographic properties enable us to construct a quantum public-key cryptosystem, which is likely to withstand any chosen plaintext attack of a polynomial-time quantum adversary. We further discuss a generalization of QSCDff, called QSCDcyc, and introduce a multi-bit encryption scheme that relies on similar cryptographic properties of QSCDcyc.

(Image from the paper.)

Quantum Information in the Mainstream

2011-03-24T19:41:00.001-07:00

It looks as if quantum information is starting to enter the mainstream: US News and World Report has an article on using diamonds for quantum memory.

Classical Simulation of Quantum Adiabatic Algorithms using Mathematica on GPUs

2011-03-12T15:40:00.001-08:00

Simulation of quantum computers is what allows us to test quantum software on a limited scale. Therefore this recent paper by Díaz-Pier, Venegas-Andraca, and Gómez-Muñoz, Classical Simulation of Quantum Adiabatic Algorithms using Mathematica on GPUs is of interest. The abstract:

In this paper we present a simulation environment enhanced with parallel processing which can be used on personal computers, based on a high-level user interface developed on Mathematica\copyright which is connected to C++ code in order to make our platform capable of communicating with a Graphics Processing Unit. We introduce the reader to the behavior of our proposal by simulating a quantum adiabatic algorithm designed for solving hard instances of the 3-SAT problem. We show that our simulator is capable of significantly increasing the number of qubits that can be simulated using classical hardware. Finally, we present a review of currently available classical simulators of quantum systems together with some justifications, based on our willingness to further understand processing properties of Nature, for devoting resources to building more powerful simulators.

(Image is figure 1 from the paper.)

More physical progress

2011-03-12T15:28:00.000-08:00

More physical progress, out of the University of Queensland.

Solid state qubits

2011-02-27T07:49:00.000-08:00

More progress on physical implementations of quantum computers: solid state qubits?

arXiv: Advances in Quantum Metrology

2011-02-16T20:06:00.000-08:00

From arXiv: Advances in Quantum Metrology by Giovannetti, Lloyd, Maccone. It is a preliminary version, but still an intriguing topic. The abstract:

In classical estimation theory, the central limit theorem implies that the statistical error in a measurement outcome can be reduced by an amount proportional to n^(-1/2) by repeating the measures n times and then averaging. Using quantum effects, such as entanglement, it is often possible to do better, decreasing the error by an amount proportional to 1/n. Quantum metrology is the study of those quantum techniques that allow one to gain advantages over purely classical approaches. In this review, we analyze some of the most promising recent developments in this research field. Specifically, we deal with the developments of the theory and point out some of the new experiments. Then we look at one of the main new trends of the field, the analysis of how the theory must take into account the presence of noise and experimental imperfections.

(The image is figure 2 from the paper.)

arXiv: Experimental Extraction of Secure Correlations from a Noisy Private State

2011-02-07T20:46:00.000-08:00

Recently revised on arXiv: Experimental Extraction of Secure Correlations from a Noisy Private State by Dobek, Karpinski, Demkowicz-Dobrzanski, Banaszek, and Horodecki:

We report experimental generation of a noisy entangled four-photon state that exhibits a separation between the secure key contents and distillable entanglement, a hallmark feature of the recently established quantum theory of private states. The privacy analysis, based on the full tomographic reconstruction of the prepared state, is utilized in a proof-of-principle key generation. The inferiority of distillation-based strategies to extract the key is exposed by an implementation of an entanglement distillation protocol for the produced state.

There is a short summarizing article here too:

The latest experiment with photonic entanglement, conducted by Polish physicists working in the consortium National Laboratory for Quantum Technologies, may be of vital importance to make quantum cryptography a more widespread technology. It has been demonstrated that secret communication based on quantum phenomena, which guarantees unconditional security against eavesdropping, can be also realized using sources of quantum entanglement considered until now to be too corrupt.

(Image taken from the paper.)

Tucci's take on programming

2011-02-07T20:41:00.000-08:00

Robert Tucci has a blog on quantum computing that he's written some good things in. I strongly agree with what he wrote today and believe all of us in the field of quantum computer programming should be following:

I try to write QC programs in a platform-independent way; i.e, a way that is independent of which particular qubit realization eventually wins the grand race for a scalable QC. Whether that be anyons or any of the many other realizations currently being tried.

Billions of entangled particles

2011-01-26T20:48:00.000-08:00

This has been making quite a bit of news lately, the entanglement of 10^10 spin pairs. (Image from the paper on Nature.) Here are a few different articles:

A qubit in a 1 cm crystal

2011-01-13T19:48:00.000-08:00

Pretty cool: Researchers store a qubit in a centimeter-long crystal.

Quantum Computing Video Lectures

2011-01-03T20:41:00.001-08:00

I'm not familiar with the author, but here's a blog post with a whole slew of quantum computing video lectures. I've seen some of them such as Deutsch's before.

Introduction to models of quantum computation and quantum programming languages

2011-01-03T20:35:00.000-08:00

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 Computing Headlines in 2011?

2011-01-03T20:19:00.000-08:00

Quantum computing is named one of the areas we might see breakthroughs in 2011 by this BBC article.

Can override the RNG in Cove's local simulation

2010-12-21T20:12:00.000-08:00

I checked in a change to Cove's local simulation yesterday that allows for the random number generator to be overridden in classes derived from the quantum register. This was inspired by some discussions I've been having with Noon Silk. My intention for this is to allow users to swap out the random number generator if desired, not to give the simulation predictable behavior for testing and such.

Building on top of Cove

2010-12-16T19:58:00.000-08:00

Noon Silk is building on top of Cove (my quantum computing framework). Specifically you should check out his "qutils" project here and his blog post about it here. For starters it can generate Cove code from qasm files, which is what I used to create the circuit diagrams in my dissertation.

Here's an example of an input:

Transformed to Cove as the output:

Nice to be this seeing done. At one point I had considered building a tool to allow you to create a circuit diagram in a GUI and generate code from it, but it was low on my list and something I never got around to doing. Nice to see this being done, I see it as an excellent tool- especially for students of quantum computer programming.

Changes to local simulation implementation of Cove

2010-12-16T19:15:00.000-08:00

I've gone through and made some changes to the local simulation of Cove. (Cove is the framework for quantum computing I've developed.) Cove separates the what needs to be provided as interfaces from the how, which is provided by implementations to those interfaces. Currently I've supplied a prototype implementation which I refer to as the local simulation implementation. This simulates a quantum computer on the local PC. This is very much a prototype, with some methods not implemented and plenty of room to improve the efficiency of the simulation, the later which has never been a goal of mine.

The change I've made to the local simulation is that the methods are now virtual. I originally intended implementations to be swapped out from one another and not built on each other. So the change to virtual methods opens up a cleaner derived implementation. There may be other changes I make to further promote building implementations on top of each other. These changes were inspired by some discussions I've been having with Noon Silk.

Nielsen and Chuang 10th Anniversary Edition

2010-12-14T20:42:00.001-08:00

Nielsen and Chuang's Quantum Computation and Quantum Information is considered to be a classic in the field. (I named it one of my top quantum computing books last year.) They're coming out with a 10th anniversary addition. You can preorder it here on Amazon, it is available at the end of January 2011. The new addition is hardcover and about what I paid for my paperback version. I recommend reading Nielsen's comments before you rush out and buy it if you already own a copy.

U of Georgia to get 2 million for quantum computing

2010-12-14T20:36:00.000-08:00

Looks like more money towards quantum computing. The University of Georgia is getting 2 million for quantum computing.

TQC 2011

2010-12-13T19:44:00.000-08:00

For those who have not seen the announcement yet: The 6th Conference on Theory of Quantum Computation, Communication, and Cryptography.

A Flowchart Language for Quantum Programming

2010-12-09T19:59:00.000-08:00

From IEEE: A Flowchart Language for Quantum Programming by Feng and Ming. Unfortunately you have to be a member to read it. Selinger did work on a quantum flow chart language back in 2004 [1], so I wonderful how unique this is? I always though visual examples of quantum programming languages portrayed quite a bit, so here's an example of Selinger's "Quantum Flow Charts" or QFC:

References
[1] P. Selinger, "Towards a Quantum Programming Language," Mathematical Structures in Computer Science vol. 14, pp. 527-586, Aug. 2004 2004.

Response to: 6 steps to building the quantum computer

2010-11-30T20:15:00.000-08:00

I came across this article by John Brandon: 6 steps to building the quantum computer. There are somethings I wanted to respond to in the article.

Step 1: Build the proof of concept
I agree that this needs to be the first step. I'm not sure what the physical implementation will be, there are several different methods being attempted.

Step 2: Increase the scale
This is a logical second step of a physical implementation- once the concept is proven it needs to be scaled up to perform useful calculations.

Step 3: Build a registry for quantum functions
I see this really as part of the first two. Many works on the software side assume you have qubits of quantum memory and your software slices it up as needed. Some of those may be temporary (or scratch) qubits, others the part of your calculation. Therefore if you have n qubits you can operate on like a section of quantum RAM, this isn't all that different from steps 1 and 2. Of course, you could model a classical computer where the results are placed into registers and moved to the RAM. This could just complicate things though. A quantum operation is required to be reversible, so if you just operate directly on a block on quantum RAM you eliminate the step of having registers.

Step 4: Create a way to store these calculations
I disagree that this step is needed, and there are flaws in this argument. The author using factoring as the example. When carrying out Shor's algorithm (factoring) we're concerned with the classical result- not the quantum. Therefore there is no need to store some intermediate quantum state. When factoring 15 into 3 and 5 for example we don't care what the intermediate quantum states may have been- we just want the answer. Notice that answer of 3 and 5 is classical, not quantum. A key part of Shor's algorithm is measurements to collapse the state. If we store the state part way we cannot carry out the example.

The argument for massive storage is also not accurate. One might need massive storage if you were trying to carry out a classical simulation of Shor's algorithm. For example one needs at least 384 qubits to factor a 128 bit (not digit) number. You can take a look at my defense slides for a quick walk through of factoring. While daunting today, hundreds, thousands, or more qubits may not be that far out of reach. Think how far we've progressed with classical computers. What if quantum ones progress at the same rate once we figure out how to make them?

Step 5: Programming techniques to find the value
I agree this is a prerequisite to useful quantum computing- but not necessarily step 5. I see no reason why we have to wait until we have physical implementations. Examining the literature shows that there are already many proposals for quantum computer programming. One of my arguments for starting work before we have practical quantum computers has always been that we can hit the ground running when they arrive instead of stumbling along as we did with classical computers.

Furthermore, I've always advocated the approach of creating a quantum framework on top of existing classical languages as opposed to new quantum languages. (My project Cove, is built on .NET for example.) If we follow this approach we don't have to throw out existing systems, we can build upon them. In database software the unsorted searching part could be replaced with one that uses a quantum framework to implement Grover's algorithm.

Step 6: Delivering the results over networks
I'm not sure if I'd include this in a list of steps. Again, the reason being that in many cases we are concerned with the classical results. We already know how to transfer classical results; I've always thought something like web services would be an ideal approach. Quantum computing could even be a service: you utilize a remote quantum computer to prepare the initial state, perform operations, measure, and get a classical result.

-----
All in all I though this was a good article, and it is good to see a stab at a comprehensive list like this. I find this especially so since it includes quantum programming, which often seems to be neglected. While I don't agree with all the points, still thought provoking- which is why I'm sharing my thoughts in this post.

Foundations of Quantum Programming

2010-11-29T20:33:00.000-08:00

Here's an interesting paper: Foundations of Quantum Programming by Ying. The abstract:

Progress in the techniques of quantum devices has made people widely believe that large-scale and functional quantum computers will be eventually built. By then, super-powered quantum computer will solve many problems affecting economic and social life that cannot be addressed by classical computing. However, our experiences with classical computing suggest that once quantum computers become available in the future, quantum software will play a key role in exploiting their power, and quantum software market will even be much larger than quantum hardware market. Unfortunately, today’s software development techniques are not suited to quantum computers due to the essential differences between the nature of the classical world and that of the quantum world. To lay a solid foundation for tomorrow’s quantum software industry, it is critically essential to pursue systematic research into quantum programming methodology and techniques.

Unfortunately it is behind a pay wall at $25- which I consider steep for a 5 page article. That being said, you can view the first 3 of the 5 pages by following the "look inside" link. I strongly agree with the point we need to focus on quantum programming techniques. This is essential if we're going to hit the ground running when viable quantum computers arrive on the scene. We don't want to spend time fumbling through programming approaches like we did in the early days of classical computers.

Purdue to get 1.5 million for QIS

2010-11-18T19:05:00.000-08:00

Purdue is getting 1.5 million to study quantum information science.

Quantum Abacus for counting and factorizing numbers

2010-11-16T20:19:00.000-08:00

Another from arXiv: Quantum Abacus for counting and factorizing numbers by Suslov, Lesovik, and Blatter. The abstract:

We generalize the binary quantum counting algorithm of Lesovik, Suslov, and Blatter [Phys. Rev. A 82, 012316 (2010)] to higher counting bases. The algorithm makes use of qubits, qutrits, and qudits to count numbers in a base 2, base 3, or base d representation. In operating the algorithm, the number n < N = d^K is read into a K-qudit register through its interaction with a stream of n particles passing in a nearby wire; this step corresponds to a quantum Fourier transformation from the Hilbert space of particles to the Hilbert space of qudit states. An inverse quantum Fourier transformation provides the number n in the base d representation; the inverse transformation is fully quantum at the level of individual qudits, while a simpler semi-classical version can be used on the level of qudit registers. Combining registers of qubits, qutrits, and qudits, where d is a prime number, with a simpler single-shot measurement allows to find the powers of 2, 3, and other primes d in the number n. We show, that the counting task naturally leads to the shift operation and an algorithm based on the quantum Fourier transformation. We discuss possible implementations of the algorithm using quantum spin-d systems, d-well systems, and their emulation with spin-1/2 or double-well systems. We establish the analogy between our counting algorithm and the phase estimation algorithm and make use of the latter's performance analysis in stabilizing our scheme. Applications embrace a quantum metrological scheme to measure a voltage (analog to digital converter) and a simple procedure to entangle multi-particle states.

Perfect eavesdropping on a quantum cryptography system

2010-11-09T20:48:00.000-08:00

From arXiv: Perfect eavesdropping on a quantum cryptography system, by Gerhardt, Liu, Lamas-Linares, Skaar, Kurtsiefer, Makarov. The abstract:

The stated goal of quantum key distribution (QKD) is to grow a secret key securely between two parties with a minimum of additional assumptions. The number of assumptions has been continuously reduced, from requiring the validity of quantum mechanics in early QKD, to more general constraints on the laws of physics in device-independent QKD. Despite steady theoretical progress in dealing with known limitations of current technology, in practice the security of QKD relies not only on the quantum protocol but on the physical implementation. A variety of attacks have been conceived to exploit weaknesses of current systems. Here we demonstrate the first full field implementation of an eavesdropper attacking an established QKD connection. The eavesdropper obtains the complete 'secret' key, while none of the results measured by the legitimate parties indicate a breach in security. This confirms that non-idealities in physical implementations of QKD can be fully exploitable.

Green: Towards a formally verified functional quantum programming language

2010-10-21T20:39:00.000-07:00

I saw this posted the other day, a PhD thesis by Green out of University of Nottingham: Towards a formally verified functional quantum programming language. This is another Haskell approach. As I said in my dissertation, I think there are serious obstacles in using a functional approach to quantum programming in a commercial development environment. Nonetheless it is good to see another quantum programming approach put out there. Here's the abstract:

This thesis looks at the development of a framework for a functional quantum programming language. The framework is first developed in Haskell, looking at how a monadic structure can be used to explicitly deal with the side-effects inherent in the measurement of quantum systems, and goes on to look at how a dependently-typed reimplementation in Agda gives us the basis for a formally verified quantum programming language. The two implementations are not in themselves fully developed quantum programming languages, as they are embedded in their respective parent languages, but are a major step towards the development of a full formally verified, functional quantum programming language. Dubbed the “Quantum IO Monad”, this framework is designed following a structural approach as given by a categorical model of quantum computation.

Quantum Game of Life

2010-10-18T20:38:00.000-07:00

Remember Conway's game of life? Here's a quantum version by Arrighi and Grattage that I came across on arXiv today. Abstract:

This research describes a three dimensional quantum cellularautomaton (QCA) which can simulate all other 3D QCA. This intrinsically universal QCA belongs to the simplest subclass of QCA: Partitioned QCA (PQCA). PQCA are QCA of a particular form, where incoming information is scattered by a xed unitary U before being redistributed and rescattered. Our construction is minimal amongst PQCA, having block size 2x2x2 and cell dimension 2. Signals, wires and gates emerge in an elegant fashion.

Quantum Computing for Molecular Energy Simulations

2010-10-06T20:01:00.000-07:00

Another one from arXiv: Quantum Computing for Molecular Energy Simulations by Whitfield, Biamonte, and Aspuru-Guzik. Another way quantum computers can be put to use besides the often cited factoring.

The abstract:

Over the last century, a large number of physical and mathematical developments paired with rapidly advancing technology have allowed the field of quantum chemistry to advance dramatically. However, the lack of computationally efficient methods for the exact simulation of quantum systems on classical computers presents a limitation of current computational approaches. We report, in detail, how a set of pre-computed molecular integrals can be used to explicitly create a quantum circuit, i.e. a sequence of elementary quantum operations, that, when run on a quantum computer, to obtain the energy of a molecular system with fixed nuclear geometry using the quantum phase estimation algorithm. We extend several known results related to this idea and discuss the adiabatic state preparation procedure for preparing the input states used in the algorithm. With current and near future quantum devices in mind, we provide a complete example using the hydrogen molecule, of how a chemical Hamiltonian can be simulated using a quantum computer.

Quantum model of the stock market

2010-09-29T20:24:00.000-07:00

From arXiv recently: A quantum model of stock market by Zhang and Huang. The abstract:

Beginning with several basic hypotheses of quantum mechanics, we give a new quantum model in econophysics. In this model, we define the wave function and the operator of the stock market to establish the Schrodinger equation for the stock price. Based on this theoretical framework, an example of a driven infinite quantum well is considered, in which we use a cosine distribution to simulate the state of stock price in equilibrium. After adding an external field into the Hamiltonian to analytically calculate the wave function, the distribution and the average value of the rate of return are shown.

This one caught my eye and I figured it was worth mentioning since I work on financial web services for Xignite. It looks like the references would be a good place to start looking for other work using models of physics to study economics.

Entanglement of 3 out of 4 qubits in a superconducting system

2010-09-29T20:13:00.000-07:00

Out of Nature: Entanglement of 3 out of 4 qubits in a superconducting system. Of course, others have done more than that, but superconducting systems seem to be more scalable- which means they have the possibility of being the first practical system.

Optical chip for quantum computing

2010-09-20T20:44:00.000-07:00

Out of the University of Bristol: Optical chip enables new approach to quantum computing.

Quantum Measurements Cannot be Proved to be Random

2010-09-08T21:24:00.000-07:00

Another one from arXiv: Quantum Measurements Cannot be Proved to be Random by Rogers. At 4 pages a quick read and thought provoking.

Quantum Tagging with Cryptographically Secure Tags

2010-09-08T21:14:00.000-07:00

I saw this on arXiv: Quantum Tagging with Cryptographically Secure Tags by Kent. I have not read it, but sounds interesting from the abstract:

Various authors have considered schemes for {\it quantum tagging}, that is, authenticating the classical location of a classical tagging device by sending and receiving quantum signals from suitably located distant sites, in an environment controlled by an adversary whose quantum information processing and transmitting power is potentially unbounded. This task raises some interesting new questions about cryptographic security assumptions, as relatively subtle details in the security model can dramatically affect the security attainable. We consider here the case in which the tag is cryptographically secure, and show how to implement tagging securely within this model.

Chinese demonstrate teleportation over 16km

2010-08-27T08:59:00.000-07:00

As described here, Chinese researchers have demonstrated teleportation over 16 kilometers. Notable part of the article:

However, one notable difference between the Chinese and American experiments is that the Beijing experiment used a blue laser for their teleportation experiments while the BBN team had been employing infrared. Both have advantages and disadvantages in range and power, but the primary difference in their applications seems to be that blue and blue-green lasers penetrate further into water and so have wider applications for sub-surface communications.

Quantum Chess

2010-08-27T08:54:00.000-07:00

This is pretty cool, quantum chess, by Akl and Wismath out of Queens University. Interesting change to the game: pieces can be in superposition, say queen and knight.

Thesis: Quantum Steganography and Quantum Error-Correction

2010-08-19T19:27:00.000-07:00

I have not read through it yet, but the topic and abstract sound interesting: Quantum Steganography and Quantum Error-Correction by Shaw out of University of Southern California. (Ph.D. thesis) Here's the abstract:

In the current thesis we first talk about the six-qubit quantum error-correcting code and show its connections to entanglement-assisted error-correcting coding theory and then to subsystem codes. This code bridges the gap between the five-qubit (perfect) and Steane codes. We discuss two methods to encode one qubit into six physical qubits. Each of the two examples corrects an arbitrary single-qubit error. The first example is a degenerate six-qubit quantum error-correcting code. We prove that a six-qubit code without entanglement assistance cannot simultaneously possess a Calderbank-Shor-Steane (CSS) stabilizer and correct an arbitrary single-qubit error. A corollary of this result is that the Steane seven-qubit code is the smallest single-error correcting CSS code. Our second example is the construction of a non-degenerate six-qubit CSS entanglement-assisted code. This code uses one bit of entanglement (an ebit) shared between the sender (Alice) and the receiver (Bob) and corrects an arbitrary single-qubit error. In the second half of this thesis we explore the yet uncharted and relatively undiscovered area of quantum steganography. Steganography is the process of hiding secret information by embedding it in an innocent message. We present protocols for hiding quantum information in a codeword of a quantum error-correcting code passing through a channel. Using either a shared classical secret key or shared entanglement Alice disguises her information as errors in the channel. Bob can retrieve the hidden information, but an eavesdropper (Eve) with the power to monitor the channel, but without the secret key, cannot distinguish the message from channel noise. We analyze how difficult it is for Eve to detect the presence of secret messages, and estimate rates of steganographic communication and secret key consumption for certain protocols.

(Image is from the paper.)

Seeing Quantum Simulators

2010-08-19T19:20:00.000-07:00

From PhysicsWorld.com: Quantum simulators revealed in fresh detail. What I found the most interesting in the article:

"A Mott insulator with exactly one atom per lattice site represents a very promising candidate for a quantum register of up to a few hundred atomic quantum bits," adds Kuhr. "However, we needed to show that we really are able to manipulate each individual atom in the structure. This is crucial for encoding and reading out qubits and we are now at the beginning of setting up the first experiments of this kind."

There is also an article in Nature here.

Wired Magazine- Tech that never took: quantum computing

2010-08-11T20:19:00.000-07:00

There's a recent story on Wired titled Tech That Never Took, within it is a short section on quantum computing (third one down here) by Tomas Hayden. It falls under the "tech that never took" category because the idea was introduced nearly three decades ago and our physical implementations are currently only a few handful of qubits at best. In the article Aaronson points out that the hard part of making a quantum computer is decoherence. When building a quantum computer you can think of this problem as basically being an unintended interaction with the environment which results in the state of the quantum computer not being maintained.

It is true that we've been working on it for a long time, but I disagree that quantum computing falls under the category of "tech that never took". It is taking us a long time because it is a really hard problem. Take another hard problem, developing the atomic bomb for example. It took a long time to create one, and we only did so when we did because of the huge amount of resources poured into the Manhattan Project. Another example is classical computers: much more than 3 decades elapsed between Charles Babbage's Difference Engine and the first real computers in the mid-twentieth century. My point is that just because it takes a long time to tackle a problem doesn't mean it will "never [take]".

Additionally we continue to make progress towards quantum computers, as I've outlined multiple times. My area is quantum software, not constructing the hardware, but I'd guess we're around a decade out from our first practical quantum computers. I'd also disagree with several of the other subjects listed in the article: nanotechnology, fusion power, personalized medicine, and self driving cars to name the most glaring ones to me. Given time, we've tackled some amazing problems, I don't see why these and quantum computing will be any different. Before 1903 there wasn't even powered flight by man, by 1969 we were landing people on the Moon.

7.5 Million in QC Funding

2010-08-10T20:34:00.000-07:00

Levy out of the University of Pittsburg received 7.5 million (in US dollars) funding from the US Department of Defense to lead a team "...to tackle some of the most significant challenges preventing the development of quantum computers...". Full article here.

The Quantum Soul?

2010-08-10T20:26:00.000-07:00

There's an article published yesterday on SFGate by Chopra and Hameroff titled Can science explain the soul? As the title implies it is pretty philosophical, but a large part of the discussion involves quantum mechanics and how they could tie in. Various interpretations and speculations on how quantum processes may have a deeper meaning are always interesting- this one is worth the quick read.

Free text: An Introductory Course on Quantum Mechanics

2010-07-26T21:14:00.001-07:00

This was just posted on arXiv the other day: An Introductory Course on Quantum Mechanics by Bram Gaasbeek. The abstract:

This is a very gentle introductory course on quantum mechanics aimed at the first years of the undergraduate level. The basic concepts are introduced, with many applications and illustrations. Contains 12 short chapters of equal length, ideal for a one term course. The license allows reuse of figures and text under the Attribution-Noncommercial-ShareAlike conditions.

I skimmed through the table of contents and some of the text: some of the early chapters definitely seems applicable to some one new to quantum computing. I know I ended up spending quite a bit of money on books when I first started researching the subject, so one posted on arXiv is certainly a plus.

arXiv: Hiding Quantum Information in the Perfect Code

2010-07-19T20:38:00.000-07:00

Here's another recent one from arXiv: Hiding Quantum Information in the Perfect Code by Shaw and Brun out of the University of Southern California. The abstract:

We present and analyze a protocol for quantum steganography where the sender (Alice) encodes her steganographic information into the error syndromes of the perfect (five-qubit) quantum error-correcting code, and sends it to the receiver (Bob) over a depolarizing channel. Alice and Bob share a classical secret key, and hide quantum information in such a way that to an eavesdropper (Eve) without access to the secret key, the quantum message looks like an innocent codeword with a typical sequence of quantum errors. We calculate the average rate of key consumption, and show how the protocol improves in performance as information is spread over multiple codeword blocks. Alice and Bob utilize different encodings to optimize the average number of steganographic bits that they can send to each other while matching the error statistics of the depolarizing channel.

As the paper says, there hasn't been much work in quantum steganography. It isn't my research area, but I think this is one of the few pieces on the subject that I've come across.

arXiv: Simulating Chemistry with Quantum Computers

2010-07-19T20:24:00.000-07:00

I came across this in today's arXiv listing: Simulating Chemistry with Quantum Computers. Here's the abstract:

The difficulty of simulating quantum systems, well-known to quantum chemists, prompted the idea of quantum computation. One can avoid the steep scaling associated with the exact simulation of increasingly large quantum systems on conventional computers, by mapping the quantum system to another, more controllable one. In this review, we discuss to what extent the ideas in quantum computation, now a well-established field, have been applied to chemical problems. We describe algorithms that achieve significant advantages for the electronic-structure problem, the simulation of chemical dynamics, protein folding, and other tasks. Although theory is still ahead of experiment, we outline recent advances that have led to the first chemical calculations on small quantum information processors.

It is well known that a simulation of a general quantum system on a classical computer experiences an exponential slow down. As the title states, this paper describes how a quantum computer can be used to avoid this problem in Chemistry.

Interview with Freedman

2010-06-29T19:49:00.000-07:00

Here is an interview with Michael Freedman of Microsoft. Freedman is driving the effort there to create a quantum computer through the Station Q group.

It is good to see Microsoft doing some work in the field. I'd figure them to be the company to really drive research into quantum computer programming, but I've yet to come across anything that indicates they're doing so. Speaking of funding research for quantum computer (programming), given the immense payoffs that will come from when we have them, I'm constantly surprised that there isn't more work and funding in the field. (Publicly at least....)

Raytheon Physical Implementation Advancement

2010-06-22T20:48:00.000-07:00

It shouldn't be too surprising given what the company is involved in, but they've made an advancement in physical implementations as outlined in their press release. The paper itself is behind a paywall here on Physical Review Letters, but luckily it is also posted here on arXiv.

Simulating Quantum Computers

2010-06-22T20:26:00.000-07:00

Here's a good blog post by Tucci: Best Heavy Duty Quantum Computer Simulators. He basically breaks them down into two categories: super computers and distributed grids (like BOINC). For anything heavy duty that is a simulation on a classical computer, those types of approaches are the only real solutions.

There are some approaches to help on a modern PC, although your still much more limited than the above. A quantum register is represented by 2^n complex numbers, where an operation on that register is a 2^n x 2^n matrix of complex numbers. The simple approach is just that, but as you can see, the memory requirements are large: you'll need 2^n complex numbers for the initial state of the register, the 2^n x 2^n complex matrix for the operation, and 2^n complex numbers for the output. One way to cut down the memory needed is to only do the matrix multiplication one row at a time. Doing so you need only 2^n complex numbers for the matrix instead of the entire thing. This is how the current implementation of Cove, my framework for programming quantum computers, currently works. Of course, there are much more elaborate tricks out there for improving the efficiency of quantum computers.

Another area I've been toying with for some time is to utilize more than one core on a system. The easiest approach with the current implementation of Cove would be just to spawn extra threads to do the matrix multiplication pieces. This would come at the cost of the extra 2^n complex numbers for each thread running. So there is a trade off between memory use and faster execution of the simulation. The execution time has been the bottle neck for a lot of the sets of a few handfuls of qubits I've been playing with, so this is something I'll probably get to eventually.

The previous paragraph being said, my goal has always been the creation of a usable framework for quantum computer programming. The simulation has always been something that will allow me to play with existing code, so my focus has never been on making it incredibly efficient.

Cove is setup where a user writes their code against a set of interfaces. With the current incarnation of Cove, the implementation is this simulation I've been talking about. The idea is however, that the simulation implementation could eventually be swapped out with one that runs on an actual quantum computer. In doing so a users code could switch between various implementations (actual quantum computer, my simulation, super computer, grid, etc) with only switching a reference and using statement.

Quantum Steganography

2010-06-16T08:57:00.000-07:00

Pretty cool: Quantum Steganography, by Shaw and Brun out of the University of Southern California's Computer Science department.

Quantum Information Processing with Adversarial Devices

2010-06-15T20:41:00.000-07:00

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.

Interview with Peter Shor

2010-06-10T19:42:00.000-07:00

Here's an interview from Dr. Dobb's with Jack Woehr interviewing Peter Shor- as in Shor's algorithm for factoring. Most discussions on quantum computing focus on the physical implementations, or perhaps algorithms. It was refreshing to see a mention of actually programming quantum computers too:

JW: I've seen quantum computer machine language simulators on the web. What would an implementation of Shor's Algorithm in a high-level quantum computing language look like?

PS: Good question. Certainly I can imagine a Fortran-style high-level language that would make Shor's Algorithm easier, but really, you'd want something more high-level than that.

That being said, I don't think the best approach will be a quantum computing language. Too much computation is classical, even when a quantum computer is used. As an example, a quantum computer is used just for a single step of Shor's algorithm- the rest is classical. Preferable to a quantum computing language I think would be a framework that extends classical languages to allow for quantum computation. There are many benefits, but I see the big two as being:

The framework designer can focus on tackling quantum computation. They don't have to try to include classical techniques that we've spent decades refining.
There is a large user base for the popular classical languages. By creating a framework there is less of a hurdle for those programmers to perform quantum computation. Furthermore it will integrate much better with existing code bases.

Of course, I developed Cove as a framework for quantum computation exactly because of the reasons above.

Geometry of abstraction in quantum computation

2010-06-07T20:52:00.000-07:00

I came across this paper by Dusko Pavlovic posted on arXiv over the weekend: Geometry of abstraction in quantum computation. Here's the abstract:

Quantum algorithms are sequences of abstract operations, performed on non-existent computers. They are in obvious need of categorical semantics. We present some steps in this direction, following earlier contributions of Abramsky, Coecke and Selinger. In particular, we analyze function abstraction in quantum computation, which turns out to characterize its classical interfaces. Some quantum algorithms provide feasible solutions of important hard problems, such as factoring and discrete log (which are the building blocks of modern cryptography). It is of a great practical interest to precisely characterize the computational resources needed to execute such quantum algorithms. There are many ideas how to build a quantum computer. Can we prove some necessary conditions? Categorical semantics help with such questions. We show how to implement an important family of quantum algorithms using just abelian groups and relations.

Adoption Issues for Quantum Information Technology

2010-06-02T20:28:00.000-07:00

Pascal Heus (at George Mason) is doing work on adoption issues for quantum information technlogy which he describes as:

This research project aims at better understanding the challenges facing Quantum Information Technology (QIT) in order to successfully integrate into the existing "classic" Information Technology (IT) framework.

You can read more about it on his site here. He also has a survey on the topic here, which I thought was good. I recommend taking the few minutes to do it if you have the time.

LED for Entangled Light

2010-06-02T19:46:00.000-07:00

Toshiba has created an "entangled light emitting diode" (ELED) which can create entangled photons. Maybe the optical approach towards quantum computing will be viable. You can read more at the ABC News article.

Electron Spin

2010-05-26T20:54:00.000-07:00

They're working on manipulating electron spin at the University of Southampton. Notable, because they could be used in physical implementation of quantum computers.

Position-Based Quantum Cryptography

2010-05-19T20:34:00.000-07:00

Here's an interesting paper: Position-Based Quantum Cryptography by Nishanth Chandran, Serge Fehr, Ran Gelles, Vipul Goyal, and Rafail Ostrovsky.You can get the paper here on arXiv and there is a good popular science summary here on Technology Review. Quantum cryptography has some great applications, adding in location makes it even more so.

Quantum Key Distribution: 1 megabit/sec, 50 km

2010-05-03T20:10:00.000-07:00

At Toshiba they've done quantum key distribution at 1 megabit a second over 50 km.

Quantum heuristic algorithm for traveling salesman problem

2010-04-28T21:39:00.000-07:00

I came across this paper on arXiv: Quantum heuristic algorithm for traveling salesman problem by Jeongho Bang, Seokwon Yoo, James Lim, Junghee Ryu, Changhyoup Lee, and Jinhyoung Lee. Here's the abstract:

We propose a quantum heuristic algorithm to solve a traveling salesman problem by generalizing Grover search. Sufficient conditions are derived to greatly enhance the probability of finding the tours with extremal costs, reaching almost to unity and they are shown characterized by statistical properties of tour costs. In particular for a Gaussian distribution of the tours along the cost we show that the quantum algorithm exhibits the quadratic speedup of its classical counterpart, similarly to Grover search.

The paper is a short read at 5 pages too. I remember discussing the traveling salesman problem in the Summer of 2007 when discussing graph theory in a survey course at Colorado Tech with Dr. Willshire, Dr. Sanden, and Dr. Calongne. It wasn't all that long after I started getting into quantum computing as my research there. I remember at the time thinking it just seemed like a problem that a quantum computer could somehow be utilized for.

US Army and NSA Supporting Quantum Computing

2010-04-28T21:33:00.000-07:00

Not too surprisingly, the US Army and NSA are looking for quantum computing proposals. There are 3 areas they're looking for, and they focus on physical implementations. Unfortunately quantum software isn't covered. As we've seen with classical computers, the physical implementation isn't much use without well written software.

Another Physical Advancement by NIST

2010-04-28T20:17:00.000-07:00

NIST has created a quantum dimmer switch, another step forward towards physical implementations of quantum computers. (NIST announcement)

True Randomness via Quantum Mechanics

2010-04-21T20:51:00.000-07:00

Not too surprisingly to those in the quantum computing field: at the University of Maryland they're utilizing quantum mechanics for true randomness. Randomness plays a key role in cryptography. If you've ever wondered why you might have to randomly hit the keyboard for awhile when generating a key, that's why- random input is trying to be gathered.

Another QC language: Q-Lisp

2010-04-14T21:09:00.000-07:00

I came across another quantum programming language: Q-Lisp. At a glance it seems similar to many of the other functional approaches I covered in my dissertation.

Supercomputer simulates QC with 42 qubits

2010-04-14T20:37:00.000-07:00

JUGENE simulates a quantum computer with 42 qubits. That may not sound impressive to those not familiar with simulating quantum computers, but it is pretty remarkable they could do that many qubits. To simulate an arbitrary quantum state requires a matrix of 2^n complex numbers to simulate n qubits. For 42 qubits that is 4,398,046,511,104 complex numbers.

Given this exponential growth, it wasn't too surprising that I ran into size constraints quickly when working on Cove. For the following example I did a simple case of putting the entire register in superposition, then measuring it. This was done on an Intel Core Duo T2300 with 1 GB of RAM maybe a year and a half ago. The jump between 9 and 10 qubits really illistrates how the exponential slow down happens in a simulation of an arbitrary quantum system.

Room Temperature Quantum Computers

2010-04-06T20:42:00.000-07:00

Sounds like they're making progress towards room temperature quantum computers as part of the EQUIND project. More details at Element Six and New Electronics. Here is the actual letter at Nature, although it is behind a paywall.

Quantum State in Large Objects

2010-03-30T20:13:00.001-07:00

From the BBC: Team's quantum object is the biggest by factor of billions.

Yet another important development towards physical implementations of quantum computers.

Vedral's New Book

2010-03-23T20:48:00.000-07:00

Vlatko Vedral has a new book out titled Decoding Reality: The Universe as Quantum Information (Amazon). From the description it looks to be a non-technical exploration, check both the links for more.

I have Vedral's 2006 book, Introduction to Quantum Information Science [1] and consult it from time to time. It went a lot deeper into some areas than I needed while doing my initial work on Cove, but nonetheless remains in my stack of quantum computing books that I consult. See my Top Books on Quantum Computing Post for the books I found most useful.

References
[1] V. Vedral, Introduction to Quantum Information Science, 1 ed. Oxford, Great Britain: Oxford University Press, 2006.

University of Waterloo’s Institute for Quantum Computing and Singapore’s Centre for Quantum Technologies

2010-03-09T20:36:00.000-08:00

University of Waterloo’s Institute for Quantum Computing and Singapore’s Centre for Quantum Technologies team up.

$900k NSF Grant for Quantum Computing

2010-03-02T20:35:00.001-08:00

In addition to the DARPA funding I mentioned a few weeks ago, the National Science Foundation has recently awarded a $900,000 grant for quantum hardware.

Quantum Mathematica Add On

2010-02-23T20:45:00.000-08:00

This was passed my way by the author, José Luis Gómez-Muñoz: a Mathematica Add On for Quantum Computing. There is also a short 6 minute video that walks you through it on youtube:

I have not played with it yet, but the video does a great job of explaining what it can do. What I especially liked was the ability to view the circuit in different forms. As an example you could view the circuit in the more traditional 2 dimensional form as well as a 3 dimensional one. Additionally you can view things in matrix form and so on.

Definitely looks like a great tool to grab images for presentations. Furthermore it would be useful for students to double check work. I had to write my own complex matrix class for Cove and it would've been nice to have an easy to use tool such as this to compare against so I could more quickly verify my implementation.

13th Workshop on Quantum Information Processing Presentations

2010-02-23T19:13:00.000-08:00

I came across this on Dave Bacon's blog last week: the presentations from the 13th Workshop on Quantum Information Processing (QIP 2010). If you're interested in the field, you're sure to find something of interest to check out.

An Invisible Quantum Tripwire

2010-02-17T20:32:00.000-08:00

I came across this paper on arXiv today: An Invisible Quantum Tripwire. It is a short read (4) pages, and pretty interesting. It basically expands the bomb experiment, where the presence of a bomb can be detected without measurement- albeit with only a 25% chance of successful detection. (That cannot be done classically.) The paper also introduces that experiment.

Manipulating Lone Qubits

2010-02-10T19:59:00.000-08:00

At Princeston Petta's demonstrated how to manipulate a lone electron. Another step forward towards physical implementations of quantum computers.

Quantum Algorithms Make Cover of Communications of the ACM

2010-02-09T20:42:00.000-08:00

Quantum algorithms made the cover of this month's (February 2010) Communications of the ACM (CACM) in an article titled Recent Progress in Quantum Algorithms by Bacon and Van Dam. Having quantum computing make the cover of CACM shows that the field is moving more and more into the mainstream.

Not only is it exciting to see the article in CACM, but it is very well written and up to date. Many of the texts on quantum computing cover Grover's and/or Shor's. This article covered playing quantum games, simulation, and Shor's in addition to the more general finding hidden symmetries. They also explain quantum computing through the quantum coin toss (which I also did in my dissertation) and the drunkard's walk. At 10 pages I'd have to describe this article as an excellent intro to quantum algorithms and recent progress being made.

DARPA and Quantum Computing

2010-02-03T21:47:00.000-08:00

DARPA (United States Defense Advanced Research Projects Agency) has a Quantum Entanglement Science and Technology (QuEST) program. You can find the website here, and is summed up well by the home page:

The objective of the QuEST program is to identify and address the most important outstanding challenges and opportunities, both experimental and theoretical, and resolve or exploit them to enable revolutionary advances in the field of quantum information science and technology.

It shouldn't be too much of a surprised that DARPA is interested in the field. I think what is noteworthy is that the budget has been steadily increasing: 4.4 million in FY2008, 9.4 in FY2009, 14.1 in FY2010. (See page 26 here for the numbers.) I recognize that this isn't much money as far as government spending is concerned, but this is just what is publicized by DARPA. Given the potential of quantum computers, I wouldn't be at all shocked if there is more work going on behind closed doors. (Someone asked me about this during my dissertation defense.)

Quantum Cellular Automata and Grover's Algorithm

2010-01-28T19:49:00.000-08:00

I just came across this paper on arXiv: "Quantum Algorithm of Evolutionary Analysis of 1D Cellular Automata" by Pavlyshenko. It is a quick read (7 pages), and basically discusses using elements of Grover's algorithm to see if certain states of a cellular automata evolution exist.

D'Hondt and Vandriessche: Distributed Quantum Programming

2010-01-20T21:19:00.000-08:00

D'Hondt and Vandriessche have posted a paper on arXiv titled Distributed Quantum Programming. The technique the paper describes is pretty mathematical, so I wouldn't classify it as a "practical" approach to quantum programming. Nonetheless, it is great to see continued work in the subject. At the end of the paper they discuss a "distributed quantum virtual machine", which is also worth checking out. Good to see details of how we may actually interact with quantum computers in standard way- taking Knill's QRAM a step farther. They also describe a GUI for the quantum virtual machine's design tool:

(Image is from the paper itself.)

Here's the abstract of the paper:

In this paper we explore the structure and applicability of the Distributed Measurement Calculus (DMC), an assembly language for distributed measurement-based quantum computations. We describe the formal language’s syntax and semantics, both operational and denotational, and state several properties that are crucial to the practical usability of our language, such as equivalence of our semantics, as well as compositionality and context-freeness of DMC programs. We show how to put these properties to use by constructing a composite program that implements distributed controlled operations, in the knowledge that the semantics of this program does not change under the various composition operations. Our formal model is the basis of a quantum virtual machine construction for distributed quantum computations, which we elaborate upon in the latter part of this work. This virtual machine embodies the formal semantics of DMC such that programming execution no longer needs to be analysed by hand. Far from a literal translation, it requires a substantial concretisation of the formal model at the level of data structures, naming conventions and abstraction mechanisms. At the same time we provide automatisation techniques for program specification where possible to obtain an expressive and user-friendly programming environment.

SA: The Next 20 Years of Microchips

2010-01-14T20:40:00.000-08:00

Scientific American has published an article in this month's (January 2010) issue titled The Next 20 Years of Microchips: Pushing Performance Boundaries. It gives a good 50,000 foot overview (about half a page each) to several areas computers will probably move into over the next decade or two. Quantum computing is mentioned as one of them, and the fact that they've been writing about the subject often recently reflects the growing interest in the field. The article also covers other topics such as optical and biological computing.

If you're a graduate student looking for a research area, I recommend checking out this article. Picking a "bleeding edge" subject means there is still a lot of work to be done- and this article mentions a lot of these subjects. This can make identifying a particular niche to fill much easier, and obviously there is less of a chance of someone doing the same thing in parallel. (A classic doctoral student fear: having someone else publish the same thing right before you finish.) Not only does it make things easier, but I personally found it extremely interesting and rewarding working on a topic that is ahead of the curve.

An Overview of Quantum Computing for Technology Managers

2010-01-04T21:17:00.000-08:00

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.

Logically manipulating qubits in Cove

2009-12-24T11:09:00.000-08:00

In Cove a collection of qubits is represented by an instance of IQuantumRegister. The logical manipulation of qubits in a register is largely inspired by Python's list manipulating, or slicing as it is called. There are a variety of ways these qubits can be logically manipulated, the following illustration demonstrates a few:

In the above the numbers represent the index is represented by numbers, just like you would with an array. The letters A - D represent specific qubits. So you can see the SliceTo(2) operation obtains indexes 0 to 2, resulting in qubits A, B, C. The SliceSubset() operation slices the current indexes to an arbitrary set. In this case the qubit at index 2 (C) will become the first one and the qubit at index 1 (A) will become the second qubit in the new slice.

It is important to point out that each of the slicing operation returns a new instance of IQuantumRegister. This means that the slices can be independently manipulated. That being said, they all share the same qubits: so the manipulation of one slice may impact another. As an example if we perform a Not operation on qubit A, it will be Not'ed in every slice.

This allows for easy applications of operations. Take a CNot (controlled not) operation for example, this is an operation on two qubits. So if we take the original register of 4 qubits and want to perform the operation on qubits A and D we can just do something like this:

MyRegister.SliceSubset(new int[] {0, 3}).OperationCNot();

The OperationCNot() will also return the slice after the operation is performed. So this example shows how operations can be chained together to manipulate the register, then discarded if needed- leaving MyRegister as the original 4 qubits after the above line of code is executed.

D-Wave and Google

2009-12-18T12:26:00.000-08:00

Google teaming up with D-Wave has been making a lot of noise lately. I wasn't originally going to write anything about it, until I came across a recent post by Scott Aaronson titled "Hopefully my last D-Wave post ever". I thought the way he wrote it was humorous- I liked the fictional interchange. I recommend reading both the post and comments.

I don't really have too much more to add other than to quote Carl Sagan: "extraordinary claims require extraordinary evidence" [1]. We're still waiting for the extraordinary evidence from D-Wave.

References

[1] C. Sagan, Billions & Billions: Thoughts on Life and Death at the Brink of the Millennium, 1 ed. New York, NY: Ballantine Books, 1997.

Why we should program quantum computers with frameworks

2009-12-08T20:39:00.000-08:00

I knew when I started my doctoral research at Colorado Tech that I wanted to do it in quantum computing. I work on software for a living, so I was thinking it would be good if I could combine the two somehow. It didn't take me long in my literature review to come across and settle on quantum computer programming as a research area as a way to blend on these two areas.

One thing really stood out to me at first: most of the existing proposals for quantum computers were languages designed for quantum computing. However, I think there are very strong reasons for creating frameworks on top of existing classical languages instead of creating new languages:

Over 8500 programming languages have been created [1], but in reality only a few see any sort of wide spread use. In my opinion, it is highly unlikely that we'll adopt new languages solely for the purpose of quantum computing.
By creating a new language the designer(s) must tackle not only the quantum issues, which are hard enough, but all the classical ones as well. We've spent years on classical languages, the focus of quantum programming design efforts should be on quantum computation, not rehashing classical problems. Tackling the classical issues as well distracts from the goal at hand.
Quantum computing is only typically utilized for part of the computation. Take Shor's algorithm for factoring [2] as an example: a quantum computer is utilized only for part of the algorithm, the rest is classical. Put that in the bigger picture of whatever software is doing the factoring and it becomes clear that quantum computing really does fit into Knill's QRAM model [3] where the quantum computer is a resource of the classical computer.
Frameworks are meant to be extended, perhaps in ways the designer didn't envision. Frameworks are much easier to extend (through hot spots [4]) by their very nature than languages are. Extending the framework can lead to more elegant solutions and more readable code as opposed to trying the bend a language to accomplish something the designer didn't intend or want to allow.

These were some of the factors that really motivated me to create Cove as a framework instead of creating yet another language. (Cove is a quantum computing framework developed as part of my Doctoral research.) That isn't to say that there aren't a lot of good lessons to be learned from languages- I drew a lot from Omer's QCL [5] as an example. I also drew a lot from Bettelli [6, 7], who also made the point that we should program quantum computers by expanding classical languages.

(I've written about this previously in my dissertation on Cove to a certain degree, this just makes it more explicit in a more condensed blog format.)

References
[1] T. J. Bergin, "A History of the History of Programming Languages," Communications. ACM, vol. 50, p. 5, May 2007 2007.

[2] P. W. Shor, "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer," SIAM Journal on Computing, vol. 26, p. 25, October 1997 1997.

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

[4] H. C. Cunningham, L. Yi, and T. Pallavi, "Framework design using function generalization: a binary tree traversal case study," in Proceedings of the 44th annual Southeast regional conference Melbourne, Florida: ACM, 2006.

[5] B. Omer, "A Procedural Formalism for Quantum Computing," in Theoretical Physics. vol. Masters Vienna: Technical University of Viena, 1998, p. 93.

[6] S. Bettelli, "Towards an architecture for quantum programming," in Mathematics. vol. Ph.D. Trento, Italy: University of Trento, 2002, p. 115.

[7] S. Bettelli, T. Calarco, and L. Serafini, "Toward an architecture for quantum programming," The European Physical Journal D - Atomic, Molecular, Optical and Plasma Physics, vol. 25, p. 19, August 2003 2003.

GHz Manipulation of Quantum States of Electrons

2009-12-03T20:56:00.000-08:00

At UC Santa Barbara they've moved forward in manipulating the state of electrons within diamonds at GHz rates. (UCSB Press release here. Page of UCSB's Center for Spintronics and Quantum Computation here.)

Lead author, Post-Doc Greg Fuchs of UCSB.

Paper: Evolution of Quantum Systems by Diagrams of States

2009-12-02T21:10:00.000-08:00

I came across this paper on arXiv, titled "Evolution of Quantum Systems by Diagrams of States" by Felloni, Leporati, and Strini. You can get the paper from arXiv here.

I've only skimmed it so far, but it is good to see this sort of thing. I suppose by the nature of things, quantum computation is very math intensive and we lack good visual representations of things. The only real two exceptions to this are quantum circuit diagrams and the Bloch Sphere. The circuit diagrams represent the application of operations to quantum registers (collections of qubits). As an example, here is the circuit diagram to construct a Sum operation from elementary operations:

The other big graphical representation we have is the Bloch Sphere. Basically this is a way of viewing the state of a single qubit on a sphere. In this the poles (of the z axis) represent |0> and |1>, and a point on the surface represents the state of the qubit. This is great for visualizing a single qubit, but doesn't scale beyond that. I wouldn't cite in a paper, but this blog is a more informal forum, so here's the link to Bloch Sphere on Wikipedia. Here's what a Bloch Sphere looks like though:

As I said, it is good to see a paper like this. The abstract the authors put together for the paper sums it up better than I would, so here it is:

We explore the main processes involved in the evolution of general quantum systems by means of Diagrams of States, a novel method to graphically represent and analyze how quantum information is elaborated during computations performed by quantum circuits. We present quantum diagrams of states for representations of quantum states by density matrices, partial trace operations, density matrix purification and time-evolution by Kraus operators. Following these representations, we describe by diagrams of states themost general transformations related to single qubit decoherence and errors.

Diagrams of states prove to be a useful approach to analyze quantum computations, by offering an intuitive graphic representation of the processing of quantum information. They also help in conceiving novel quantum computations, from describing the desired information processing to deriving the final implementation by quantum gate arrays.

NIST Creates a 2 Qubit Programmable Quantum Computer

2009-11-15T14:21:00.000-08:00

At the National Institute of Standards and Technology (NIST) they've done it again: they've created a 2 qubit programmable quantum computer. The key word here is programmable, it can carry out an arbitrary sequence of operations. We still need to scale things up, but this is another important milestone.

(NIST Post doc David Hanneke doing a demo of the quantum computer. Image from NIST.)