Tuesday, November 30, 2010

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.

Monday, November 29, 2010

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.

Tuesday, November 16, 2010

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.

Tuesday, November 9, 2010

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.