rose.blog

Is there an accepted measure of entanglement for a given k-qubit state when k>2?

Big ups to Dangerous Dan Henderson for winning the Pride middleweight title!!! I had the good fortune to train with Dan for a few months prior to the 1996 Olympics… damn that was a fun camp. Dan’s a good guy, glad to see him doing so well in MMA… although the more my old training buddies rip it up in MMA the more I think maybe I could still make a run at it…

Here’s a clip of Dan taking it to the Axe Murderer Wanderlei Silva.

Now that the dust has settled from the demo of one of our 16-qubit systems, I thought it might be generally of interest to do a little recap.

First: the technology. Orion has been remarkably rock solid. For such a complex machine, we haven’t seen a single systems failure yet, even during the obvious time for such a failure (live demos). So kudos to the entire technical team, the machine is solid! Word.

Second, some numbers:

• We had in excess of 600 people attend the two events (Mountain View, Vancouver); we had to turn people away at the Vancouver event as we had more than double the registered attendees show up
• More than 300 press articles were written about the demo, including articles in Scientific American, The Economist, Nature, Science, and national news coverage on CNN and NBC
• More than 2,300 blog articles have been written about the event
• We have had over 100 respondents with ideas for applications to date, about 1/3rd of which are from Fortune 1000 companies

Third, I thought I’d mention some of my favorite quotes and whatnot emerging from the demo.

Favorite article: My favorite was The Economist article, because it was the source of most of the people with applications ideas

Favorite blog caption: Without a doubt, this one.

Favorite quote: Probably the roast beef sandwich quote.

Best music to listen to while debugging Orion’s DAC boards: Probably this.

Best use of barbeque in getting Orion working: Sergey’s kabobs.

Best motivational use of an effigy of Eric: Well that’s obvious.

Best supporting actor: Squidbucks.

For everyone involved in making the demo a great success, big thanks!

Now on to the next generation…

What do I mean by red herring, you might ask?

The etymology of the phrase may be the practice of saving a hunted fox by dragging a smoked herring across its trail - creating a new, useless scent trail. When smoked, herring turns bright red and is quite odoriferous. The latter trait made it possible to deliberately leave a strong trail on the ground to facilitate training hounds to track a scent. Having been so trained, hounds would readily follow the scent of the fish over that of the fox, allowing their quarry to escape.

Analogy clarification:: Fish –> factoring; Fox –> ever other application of QCs.

Scott Aaronson over at Shtetl-optimized recently posted a great description of Shor’s algorithm for non-specialists, in response to a request from JR Minkel, a Scientific American writer. Even though Scott has an alarming lack of musical taste he has few peers when it comes to describing complex technical issues to non-specialists.

The premise of Shor’s algorithm is this: take one (large) QC, one large product of prime numbers, shake well, out comes the factors of the large product of primes.

The algorithm is interesting because it produces this output (the factors) much faster than you can without a QC. It is also possibly interesting from the applications perspective because the problem it solves is important for certain types of code-breaking.

There is a particular type of encryption in use that uses the “hardness” of factoring large products of prime numbers to keep data secure. This particular approach would become vulnerable in a world with large QCs.

So let’s say we lived in a world with factoring machines available at Walmart. Would internet commerce collapse? Of course not. The most likely thing that would happen is that encryption software providers–the people who keep your credit card numbers secure–would change the “hard” part of their encryption to something that (1) wasn’t factoring and (2) was impervious to QCs. Is this technically possible? Absolutely. Also over time it’s likely that encryption — even retail encryption — will migrate over to quantum encryption.

So you might ask why the NSA cares about factoring at all. I can only speculate, but here are three possible reasons: (1) they have a mandate to be at the leading edge of understanding all things cryptanalytic, regardless of practical application; (2) the possibility that messages encrypted today have been stored somewhere and will be decrypted in 5-10 years with some new advanced technology (QC); (3) they are concerned that new non-factoring crypto algorithms will be developed.

Alright so why am I going on about this? The reason is that when asked what QCs are good at, many QC experts respond with the factoring example, when there are several other perfectly great quantum algorithms that would also fit the bill. Why the focus on factoring? I’m not entirely sure, but here are two possible reasons: (1) how the algorithm works is technically very interesting (when people understand it, they usually say, man that’s cool!); (2) usually researchers are financed by the NSA, so it’s self-serving to put a line in the intro to your paper that lists code-breaking as an application, and then every paper written about QC starts with the same sentence, and the meme takes hold.

Why does it matter that experts focus on factoring? There are two reasons. The first is that factoring isn’t interesting from the applications/commercial perspective. It is hard to imagine how a company could become successful building machines that did nothing but factor products of primes.

The second reason is that the application is very negative in the sense that it makes the world worse than it was before the tech was introduced. There is no social benefit to adding factoring to the list of things humans can do well (or if there is, I haven’t heard anyone mention it). This “no social benefit” issue is often ignored by scientists and technologists, but I think this is a huge mistake. Most people feel great about supporting technologies with a clear social benefit (cures for cancer, etc.); not so much for weapons.

I think it would do the whole QC field a lot of good if the people “out there” who aren’t experts could hear about the algorithms/applications that stand a chance of creating real value, like quantum simulation, or possibly applications of the recent NAND tree algorithm, or optimization.

Whenever people ask what QCs can do, there’s a tendency for people to respond with the factoring example, which I think is making it very difficult for any non NSA people (ie pretty much everybody) to get excited about QCs. It’s hard to get really excited about something that’s both commercially worthless and has no positive social upside.

If the scientists & management at Merck/Pfizer/Exxon/DE Shaw/Amgen/Corning/Dow etc. understood (in the same way the NSA understands Shor’s algorithm) that QCs could exponentially speed up their quantum chemistry calculations there would be 100s of millions of dollars of investment from these sources flowing into practical QC R&D. This is a wonderful thing called market pull which would benefit everybody in the QC field, even if you don’t personally care about actually getting these machines into the hands of end users.

In contrast to factoring, quantum simulation is both extremely commercially valuable (a large fraction of the world’s supercomputer cycles are currently spent solving the Schrodinger equation) and offers the possibility for huge social good (new clean energy sources, better medicines, cleaner chemical plants, etc.).

Maybe it’s time to put away the fish.

I’ve got some requests for the seating planning software we used in the demo. You can find it here. It is quite cool, check it out.

Lots of hits today! To help everybody understand what we’re doing I’ve linked here to some great scientific papers that review AQC & some algorithmic stuff. They are all pretty easy to follow as these things go.

Finding cliques by quantum adiabatic evolution

A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem

Scalable Architecture for Adiabatic Quantum Computing of NP-Hard Problems

Scalable Superconducting Architecture for Adiabatic Quantum Computation

Hope these are helpful!

In my last post, a reader asked an excellent question that I thought I’d provide my perspective on. This particular issue is complex, so bear with me. Here’s the question:

If quantum computing is eventually bound to change and transform the computing business landscape completely, how come that companies with deep pockets like Intel and IBM are not planning any version of quantum computer any time soon, but they still focus only on traditional computing? If your work is worthwhile, why a company such intel, which can throw US$4 billion into a fab, can not spend a hundreth of this money to finance DWave (editor’s note: or any effort, including an internal one)?

There are at least three good reasons why a big company would decide not to invest in quantum computing as it’s currently perceived. The first is an economic argument based on the time value of money. I have a great article on this by HP’s Stan Williams that anyone interested in this question should read. Here it is:

stan_williams_qc_investment.pdf

The punchline is that any opportunity sufficiently far away with sufficient risk isn’t a good investment regardless of the size of the opportunity.

The second good reason is covered in Clay Christensen’s The Innovator’s Dilemma, which is another must-read for understanding the dynamics of technology strategy in big companies. The main point is that businesses acting rationally produce products that their customers ask for. It’s not rational to produce something that no-one wants. Major disruptive technologies are sometimes things that no-one is asking for (like QCs). This is related to the first reason. People working on QCs seem to think that companies like IBM etc. will try to build these just because they are cool. That’s not the way this type of thing works. People invest in technology development because they believe people will want to buy it. What argument would someone inside IBM use to justify a long-term high-risk high-expense internal QC effort? If there were clear large-market applications where you could definitely say, if we built this we would own a new $10B/year market with 100% margins then maybe you could justify the investment. But currently there is an extreme lack of clarity “out there” on the issue of what you’d do with a QC if you had one.

The third good reason was pointed out by a respondent to the original question. If you’re an IBM, HP, etc., it makes a lot of sense to argue as follows: Look, we don’t know at least two things. One, we don’t know what the roadmap for QC development looks like. Some say QCs will never be built. Most people say machines competitive with conventional approaches are 20 years away. Some people say 5. Some (ie me) point out that QCs are already being sold (NMR QCs) at high margins. Two, we don’t know what the market looks like. What are the applications? Who are the customers? What’s the size of the opportunity over time? So given both enormous technical and market risk, let’s do the following. Let’s wait and see what happens. If a competitor or a start-up can actually demonstrate (1) sufficient reduction of technical risk, (2) a clear path to real scalability (note: I don’t mean scalability in the sense that it’s sometimes used in research articles, ie. in principle scalable, I mean practically scalable), and (3) clear market information, most likely in the form of paying customers and a high margin business model with high growth (~40%+ year over year revenue growth), then these big guys figure that they can always get in on the action by partnering, acquiring, licensing, etc. It is rational to pay more for less risk. If I were the CEO of IBM, given the information currently publicly available, that’s certainly the strategy I would use.

Given these types of arguments, you might ask why it makes sense to try to build QCs in a business context at all. In other words, why would a start-up attempt to do this? Here’s some reasons:

1. There are several well-known case studies of situations where the prevailing wisdom about how long it would take to develop a new technology or achieve a scientific milestone were wrong. Here’s two: sequencing the human genome (Celera) and producing synthetic insulin (Genentech): here’s a Genentech case study very relevant to QC & D-Wave: scott_stern_1.pdf
2. If, as in the case of Celera or Genentech, the prevailing wisdom as to timescales to deployment could be shortened by a factor of 5 by a focused effort, then we’re talking about QCs competitive with conventional approaches in 1-4 years, not 5-20. This drastically changes the conclusions of the time value of money argument (reason #1 above).
3. Most of the people working in quantum information science aren’t even remotely interested in applications. There is a lot of interest in algorithms, and sometimes people interchangeably use the two terms, but there is a major fundamental difference between the two. This lack of interest in applications is a green field opportunity for a start up. If there are big market applications for QCs in practice, the fact that there simply aren’t a lot of people looking to connect technology to users means that a small focused effort stands a good chance at identifying these in advance of competitors. Therefore reason #2 above related to the innovator’s dilemma is actually an extremely valuable advantage for a start up. We can prospect without worrying about competition from incumbents.
4. Building QCs, especially in a business context, is extremely hard. The only way any effort has a chance of succeeding is by having a lot of A+ people in a wide range of roles. A first mover has a big advantage here. If someone wants to be involved in a really serious, long-term, well-financed effort with the kind of infrastructure required to do this very hard thing, there simply aren’t a lot of options for where to go. As an example, would I personally have joined Celera or Genentech in their early days if I had the chance? You bet I would. The same dynamic is at work now in QC development.