Wednesday, April 28, 2010

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)

Wednesday, April 21, 2010

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.

Wednesday, April 14, 2010

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.

Tuesday, April 6, 2010

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.