Can override the RNG in Cove's local simulation

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

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

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

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

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

TQC 2011

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

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

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

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

Purdue is getting 1.5 million to study quantum information science.

Quantum Abacus for counting and factorizing numbers

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

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

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

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

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

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

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

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

Quantum Measurements Cannot be Proved to be Random

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

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

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

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

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

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

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

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?

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

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

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

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

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

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

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

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

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

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:

1. 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.
2. 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

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

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

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

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

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

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

Quantum heuristic algorithm for traveling salesman problem

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

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

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

True Randomness via Quantum Mechanics

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

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

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

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

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

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

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

$900k NSF Grant for Quantum Computing

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

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

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

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

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

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

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

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

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

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

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.