Monthly Archives: April 2013

So You Want to Learn About Quantum Computing?

Quantum Computing, Quantum Mechanics, Uncategorized, ,

“Students will learn by inhabiting an alternate history where Alan Turing and Richard Feynman meet during World War II and must invent quantum computers to defeat Nazi Germany. As a final project, they will get to program a D-Wave One machine and interpret its results.”

If you are based in Seattle then you want to keep an eye out for when Paul Pham next teaches the Quantum Computing for Beginners course that follows the exciting narrative outlined above.

For everybody else, there is EdX‘s CS191x Quantum Mechanics and Quantum Computation course.  I very much hope this course will a be a regular offering.  Although it lacks the unique dramatic arche of P.Pham’s story line this course is nevertheless thoroughly enjoyable.

When I signed up for this course, I didn’t know what to expect.  Mostly, I decided to check it out because I was curious to see how the subject would be taught, and because I wanted to experience how well a web-based platform could support academic teaching.

This course fell during an extremely busy time, not only because of a large professional work load, but also because the deteriorating health of my father required me to fly twice from Toronto to my parents in Germany.  Despite this, the time required for this course proved to be entirely manageable.  If you have an advanced degree in math, physics or engineering, and want to learn about Quantum Computing, you shouldn’t shy away from taking this course as long as you have an hour to spare each week.  It helps that you can accelerate the video lectures to 1 1/2 normal speed (although this made Prof. Umesh Vazirani sound a bit like he inhaled helium).

Prof. Vazirani is a very competent presenter, and you can tell that a lot of thought went into how to approach the subject, i.e. how to ease into the strangeness of Quantum Mechanics for those who are new to it. I was suspicious of the claim made at the outset, that the required mathematics would be introduced and developed as needed during the course, but it seems to me that this was executed quite well. (Having been already familiar with the required math, I don’t really know if it’ll work for somebody completely new to it, but it seems to me that indeed the only pre-requisite required was a familiarity with linear algebra).

It is interesting to see discussions posted by individuals who took the course and were apparently subjected to QM for the first time.  One such thread started this way:

“I got 100. It was really a fun. Did I understand anything? I would say I understood nothing.”

To me this illuminates the fact that you simply cannot avoid the discussion of the interpretation of quantum mechanics.  Obviously this subject is still very contentious, and Prof. Vazirani touched on it when discussing the Bell inequalities in a very concise and easy to understand manner.  Yet, I think judging from the confusion of these ‘straight A’ students there needs to be more of it.  It is not enough to assert that Einstein probably would have reconsidered his stance if he knew about these results.  Yes, he would have given up on a conventional local hidden variable approach, but I am quite certain his preference would have then shifted to finding a topological non-local field theory.

Of course, there is only so much that can be covered given the course’s duration. Other aspects there were missing: Quantum Error Correction, Topological and Adiabatic Quantum Computing and especially Quantum Annealing.  The latter was probably the most glaring omission, since this is the only technology in this space that is already commercially available.

Generally, I found that everything that was covered, was covered very well.  For instance, if you ever wondered how exactly Grover’s and Shor’s algorithms work, you will have learned this after taking the course. I especially found the homework assignments wonderful brain teasers that helped me take my mind off of more worrisome issues at hand.  I think I will miss them. They were comprised of well thought out exercises, and as with any science course, it is really the exercises that help you understand and learn the material.

On the other hand, the assignments and exams also highlighted the strengths and weaknesses of the technology underlying the courseware.  Generally, entering formulas worked fine, but sometimes the solver was acting up and it wasn’t always entirely clear why (i.e. how many digits were required when giving a numerical answer, or certain algebraically equivalent terms were not recognized properly).  While this presented the occasional obstacle, on the upside you get the immediate gratification of instance feedback and a very nice progress tracking that allows you to see exactly how you are doing. The following is a screenshot of my final tally. The final fell during a week in which I was especially hard pressed for time, and so I slacked off, just guesstimating the last couple of answers (with mixed results).  In comparison to a conventional class, knowing exactly when you have already achieved a passing score via the tracking graph makes this a risk- and stress-free strategy.

Screen Shot 2013-04-27 at 11.56.31 AMA common criticism of online learning in comparison to the established ways of doing things is the missing classroom experience and interaction with the professor and teaching staff.  To counter this, discussion boards were linked to all assignments, and discussion of the taught material was encouraged.  Unfortunately, since my time was at a premium I couldn’t participate as much as I would have liked, but I was positively surprised with how responsive the teaching assistants answered questions that were put to them (even over the weekends).

This is all the more impressive given the numbers of students that were enrolled in this course:

The geographic reach was no less impressive:

Having being sceptical going into this, I’ve since become a convert.  Just as Khan Academy is revolutionizing the K12 education, EdX and similar platforms like Cousera represent the future for academic teaching.

 

Stretching Quantum Computing Credulity

D-Wave

Update: Corrected text (h/t Geordie)

My interest in D-Wave prompted me to start this blog, and it is no secret that I expect the company to deliver products that will have a significant impact on the IT market. Yet, to this day, I encounter the occasional low-information posters in various online forums who dismiss the company, smugly asserting that they are fraudulent and only milk their investors.

08-finanzbetrugIt would be one thing if you’d only encounter some hold-outs on Scott Aaranson’s blog, which originally emerged as the most prominent arch-nemesis before he moderated his stance.  But it’s actually an international phenomenon, as I just came across such a specimen in a German IT forum.

To understand where these individuals are coming from, it is important to consider how people usually go about identifying a “high tech” investment scam.  The following list makes no claim to be complete, but is a good example of the hierarchy of filters to forming a quick judgment (h/t John Milstone):

  1. Claims of discovering some new physics that has been overlooked by the entire scientific world for centuries. (For each example of this actually happening, there are hundreds or thousands of con men using this line).
  2. Eagerness to produce “demos” of the device, but refusal to allow any independent testing. In particular, any refusal to even do the demos anywhere other than his own facilities is a clear warning sign (indicating that the facilities are somehow “rigged”).
  3. Demos that only work when the audience doesn’t contain competent skeptics.
  4. Demos that never demonstrate the real claims of the “inventor”.
  5. Lying about business relationships in order to “borrow” credibility from those other organizations.
  6. Failing to deliver on promises.
  7. Continually announcing “improvements” without ever delivering on the previous promises. This keeps the suckers pacified, even though the con man is never actually delivering.

One fateful day, when D-Wave gave an initial presentation to an IT audience, they inadvertently set a chain in motion that triggered several of these criteria in the minds of a skeptical audience.

Of course D-Wave never claimed new physics, but ran afoul of theoretical computer science when claiming that its computer can efficiently take on a NP hard problem, given as a Sudoku puzzle irritated theoretical computer scientists when claiming that its computer can take on a Sudoku puzzle (the latter is known to be NP hard.) (#1). [Ed. Changed wording to make clear that D-Wave didn’t explicitly claim to efficiently solve NP hard Soduko.]

At the time, D-Wave was still not ready to allow independent testing (#2) and the audience did not contain theoretical computer scientists who would have challenged scrutinized the company’s claims (#3).

Subsequently, critics questioned how much the quantum computing chip was actually engaged in solving the demonstrated Sudoku puzzle, since a normal computer was also in the mix.  Scott Aaranson also pointed out that there was no way of knowing if actual entanglement was happening on the chip, and as such the demo wasn’t proving D-Wave’s central claim (#4).

To my knowledge, D-Wave never misrepresented any business relationships, but touting their relationship with Google may have inadvertently triggered criteria #5 in some people’s minds.

Although D-Wave has been rapidly increasing their chip’s integration density, and are now shipping a product that I expect to outperform conventional hardware, they didn’t deliver as quickly as initially anticipated (#6).

Criteria #7 held until they shipped the D-Wave One to Lockheed, and this marked the turning point after which the pattern rapidly unraveled.  Only people who haven’t paid attention could still hold on to the “investment fraud” canard:

  • D-Wave published internals of their machine in Nature and co-authored several papers that utilize their machine for research as diverse as Ramsey number calculations and protein folding.
  • Independent testers are now able to test the machine.  I can verify that the one tester I am corresponding with is a top notch academic from one of the best engineering and science faculties this world has to offer.  He is also fiercely independent, believing that he can outperform the D-Wave machine with hand-optimized code on a conventional chip.
  • The central claim that their chip is a true quantum chip leveraging massive qubit entanglement has been proven.

It’s time for the IT audience to come to terms with this.

Quantum computing has arrived.  It’s real. Better get used to it.

 

 

If a Fighter Writes a Paper to go for the Kill …

Popular Science, Quantum Cryptography,

You don’t want to take on this man in the rink:

And you don’t want to take on his namesake in the scientific realm.

In my last post I wrote about the Kish Cypher protocol, and was wondering about its potential to supplant Quantum Cryptography.

The very same same day, as if custom ordered, this fighter’s namesake, no other than Charles Bennett himself, published this pre-print paper (h/t Alessandro F.).

It is not kind on the Kish Cipher protocol, and that’s putting it mildly.  To quote from the abstract (emphasis mine):

We point out that arguments for the security of Kish’s noise-based cryptographic protocol have relied on an unphysical no-wave limit, which if taken seriously would prevent any correlation from developing between the users. We introduce a noiseless version of the protocol, also having illusory security in the no-wave limit, to show that noise and thermodynamics play no essential role. Then we prove generally that classical electromagnetic protocols cannot establish a secret key between two parties separated by a spacetime region perfectly monitored by an eavesdropper. We note that the original protocol of Kish is vulnerable to passive time-correlation attacks even in the quasi-static limit.

Ouch.

The ref’s counting …

Quantum Cryptography Made Obsolete?

Popular Science, Quantum Cryptography
The background story.

Electrical engineering is often overshadowed by other STEM fields. Computer Science is cooler, and physics has the aura of the Faustian quest for the most fundamental truths science can uncover.  Yet, this discipline produced a quite remarkable bit of research with profound implications for Quantum Information Science.  It is not very well publicized. Maybe that is because it’s a bit embarrassing to the physicists and computer scientists who are heavily vested in Quantum Cryptography?

After all, the typical, one-two punch elevator-pitch for QIS is entirely undermined by it. To recap, the argument goes likes this:

  1. Universal Quantum Computing will destroy all effective cryptography as we know it.
  2. Fear not, for Quantum Cryptography will come to your rescue.

Significant funds went into the latter.  And it’s not like there isn’t some significant progress, but what if all this effort proved futile because an equally strong encryption could be had with far more robust methods?  This is exactly what the Kish Cypher protocol promises. It has been around for several years, and in a recent paper, Laszlo Bela Kish discusses several variations of his protocol that he modestly calls the Kirchhoff-Law-Johnson-(like)-Noise (KLJN) secure key exchange – although otherwise it goes by his name in the literature. A 2012 paper that describes the principle behind it can be found here.  The abstract of the latter makes no qualms about the challenge to Quantum Information Science:

It has been shown recently that the use of two pairs of resistors with enhanced Johnson-noise and a Kirchhoff-loop—i.e., a Kirchhoff-Law-JohnsonNoise (KLJN) protocol—for secure key distribution leads to information theoretic security levels superior to those of a quantum key distribution, including a natural immunity against a man-in-the-middle attack. This issue is becoming particularly timely because of the recent full cracks of practical quantum communicators, as shown in numerous peer-reviewed publications.

There are some commonalities between quantum cryptography and this alternative, inherently safe, protocol.  The obvious one is that they are both key exchange schemes; The more interesting one is that they both leverage fundamental physics properties of the systems that they are employing.  In one case, it is the specific quantum correlations of entangled qubits, in the other, the correlations in classical thermodynamic noise (i.e. the former picks out the specific quantum entanglement correlations of the systems density matrix, the latter only requires the classical entries that remain after decoherence and tracing of the density matrix).

Since this protocol works in the classical regime, it shouldn’t come as a surprise that the implementation is much easier to accomplish than when having to accomplish and preserve an entangled state. The following schematic illustrates the underlying principle:

Core of the KJLN secure key exchange system. Alice encodes her message by connecting these two resistors to the wire in the required sequence. Bob, on the other hand, connects his resistors to the wire at random.

The recipient (Bob) connects the wire at random in predefined synchronicity with the sender (Alice).  The actual current and voltage through the wire is random, ideally Johnson noise. The resistors determine the characteristic of this voltage, Bob can determine what resistor Alice used because he knows which one he connected, but the Fluctuation Dissipation Theorem ensures that wire-tapping by an attacker (Eve) is futile.  The noise characteristics of the signal ensure that no information can be extracted from it.

Given that the amount of effort and funding that goes into Quantum Cryptography is substantial (some even mock it as a distraction from the ultimate prize which is quantum computing), it seems to me that the fact that classic thermodynamic resources allow for similar inherent security should give one pause.  After all, this line of research may provide a much more robust approach to the next generation,”Shor safe”, post quantum encryption infrastructure.