Quantum Bayesian Networks

January 29, 2011

The Great Communicator: the CNOT

Filed under: Uncategorized — rrtucci @ 8:16 pm

Political commentators dubbed Ronald Reagan (USA president from 1981 to 1989) “the Great Communicator”. You may or may not agree that he deserved that accolade, but in quantum information theory, there is no doubt, at least in my mind, that one particular operator deserves the title of Great Communicator more than any other: the CNOT.

The building blocks of “information” are bits in the classical world and qubits (quantum bits) in the bizarro world of quantum mechanics. You can transform a single qubit by rotating it with a U(2) transformation. But you also need to invent a really simple, unitary, 2-body interaction to send messages from one qubit to another. That’s what a CNOT (controlled not) does. In concise notation explained here, a CNOT can be expressed as \sigma_X(\tau)^{n(\kappa)}, where \kappa labels the control qubit, \tau labels the target qubit, \sigma_X(\tau) is a Pauli matrix, and n(\kappa) is a number operator.

Any unitary operation acting on any number of qubits, can be expressed as a sequence of elementary gates that are either single-qubit rotations or CNOTs. The time complexity of a quantum circuit can be measured by expressing it in terms of these elementary gates and then counting the number of CNOTs. A CNOT can send classical or quantum messages and it can entangle two qubits. Much of Shannon information theory, both quantum and classical, concerns counting how many CNOTs connect the labs of Alice and Bob.

Advertisements

January 26, 2011

Quantum Computing and Steve Jobs

Filed under: Uncategorized — rrtucci @ 6:15 am


I try very hard to keep the posts in this blog focused on the topic of quantum computing. So what does Steve Jobs have to do with that topic?

People often give you a line of BS about how it will take us at least 20.31 years to develop QCs, because, oh, it’s “so hard to do”. I believe that the speed of QC development will depend strongly on how many people like Steve Jobs we manage to enlist into the QC ranks (i.e., people who approach the QC field with the vision, energy, courage, tenacity, and urgency of a Steve Jobs).

Stevo is not perfect. Some might say he is just a glorified appliance salesman, not a scientist or a nerd. By some accounts, he can sometimes be narcissistic, ruthless, abusive, petty, and mercurial. A real pain in the ass. But I think focusing only on the lesser traits of this man would be missing the point. Steve Jobs has undoubtedly gotten a few things right in his lifetime.

A famous quote from Steve is “Real artists ship”, meaning that artists, including computer hardware and software developers, must get their products shipped to their customers in a timely fashion, or else they are not true artists. The people working to build a scalable QC should also try to achieve their goal promptly, not in 20 years, for God’s sake. We can do much better than that if we really try.

And one more thing… Steve never tires of reminding us how extremely important software is for computers. According to Steve,

“If you take away the software from the iPhone, all you’ve got left is a fancy paper weight”.

Okay, I just made that quote up, but it’s very much in the spirit of what Steve believes. Personal computers only exploded in the market once they included a few killer apps (e.g., VisiCalc (the precursor of the Excel spreadsheet), and video games like Space Invaders). Likewise, quantum computers will be dead on arrival unless they arrive already loaded with at least one compelling killer app. So what will the first killer applications for QCs look like? Probably not Shor’s algorithm. Most people don’t give a hill of beans about factoring large numbers. It’s very likely that long before QCs arrive on the scene, the use of cryptographic codes that can be broken with Shor’s algorithm will be replaced by the use of classical (not quantum) codes that already exist and which cannot be broken with QCs. (look up Post-Quantum cryptography)

Other insanely great traits of Steve Jobs that quantum computerists would do well to emulate, are

  • Steve Jobs is a very persuasive salesman. He truly believes in what he is selling. Just go to WikiQuote and read some of the quotes attributed to him, or listen to one of his speeches on YouTube, to see how persuasive he can be. Back in 1981, one of the first engineers employed by Apple invented a term, inspired by Star Trek, to describe this effect: he called it Steve’s “reality distortion field“. The term is still used today, sometimes half-mockingly, but always with implicit admiration, to describe Steve.
  • Steve Jobs is a very adept businessman, as is obvious from his successes.
  • Steve Jobs is a special kind of businessman, one that loves technology and understands it well, often in minute detail.
  • Steve Jobs understands and loves good design and high quality. He tries to make products that perform their function efficiently and yet are also beautiful at the same time; products that are easy to understand and use, and always work flawlessly.
  • Steve Jobs understands the value of constantly innovating. He was able to pull Apple away from the brink of bankruptcy, in large measure by innovating new products.
  • Steve Jobs understands the value of surrounding himself with very smart and creative people.
  • Steve Jobs is a very effective and inspiring leader of his employees. By many accounts, he is obsessively meticulous/picky, persistent and demanding. Using rewards, cajolery, and sometimes also abuse and insult, he has been able to prod/coax, time and again, his engineers to go far beyond the limits of what they thought they could do.
  • Steve Jobs knows when to pull the plug on a technology that has been superseded by a better one, or a technology that is not yet practical, or never will be. (e.g., floppy disk drives, the Newton, IBM PowerPC chips). I hope the advocates of NMR quantum computing, quantum money, a quantum internet and quantum cryptography will be just as wise. It doesn’t mean Steve gives up on computers when he pulls the plug on something. He just moves on to the next innovation.
  • Steve Jobs understands what people need and/or want. He greatly boosted revolutions in the following technological areas: computer GUI (graphical user interface) and fonts (the Mac), computer animation (Pixar), modernizing the Sony Walkman concept (the iPod), online sales of music (iTunes), smart phones and multi-touch screens (iPhone), tablets and e-book readers (iPad), etc., etc. The guy has a Midas touch when it comes to technological products.
  • Steve Jobs is very adept at advertising. Like many people, I intensely dislike most advertisements, but I have to admit that some of the coolest graphics and advertisements I’ve ever seen have come from Apple.
  • Steve Jobs is a partial vegetarian (eats no meat except fish) (Okay, I’m biased on this subject. I’m a vegetarian too)
  • Steve Jobs made an incredible comeback in his professional life.
  • Steve Jobs wears a super-hero outfit, like the Incredibles. Not spandex. A black long-sleeved turtleneck, blue jeans and running shoes.

There’s an old Wayne Gretzky quote that I love. ‘I skate to where the puck is going to be, not where it has been.’ And we’ve always tried to do that at Apple. Since the very very beginning. And we always will.
—Steve Jobs

Hear hear! from all quantum computer dreamers.

I highly recommend that you read the following:

January 12, 2011

A New Everest: Relativistic Quantum Shannon Information Theory

Filed under: Uncategorized — rrtucci @ 4:36 pm

In my previous blog post, I raved about the remarkable progress that has been made in the last 20 years in the field of quantum SIT (Shannon Information Theory). But a physicist’s work is never done. While much work remains to be done in non-relativistic quantum SIT, we can already see, looming in the horizon, a commandingly high peak awaiting to be climbed for the first time.

Special relativity and quantum mechanics were merged long ago. This process started with P.A.M. Dirac’s monumental 1928 paper entitled “The Quantum Theory of the Electron”, where he first introduced the Dirac equation. Then Schwinger, Feynman, Tomonaga and others developed QED (Quantum Electrodynamics). Even later others developed Quantum Gauge Field Theories and the Standard Model.

Merging special relativity and quantum mechanics to produce what we now call high energy physics or relativistic quantum field theories, has been an immensely productive endeavor. Perhaps merging special relativity and quantum SIT will prove to be productive too. The Dirac of SIT may be writing his monumental paper as we speak. Maybe someday this will yield some non-trivial insights into quantum gravity and String Theory.

January 10, 2011

The Continents of Quantum Mechanics and Shannon Information Theory Are Now Colliding and Merging

Filed under: Uncategorized — rrtucci @ 4:22 pm

When continents collide (suture between India and Asia in the Himalayas)


How can one explain the intricate emission spectra of atoms and molecules? Why are atoms stable in the first place? Classical physics cannot answer these questions in a satisfactory way. One needs quantum mechanics to do so.

Quantum Mechanics underlies most discoveries in physics and chemistry of the 20th century. The following areas of physics use quantum mechanics intensively:

statistical mechanics, solid state physics (semiconductors, superconductors, superfluids), laser physics, quantum field theory, particle physics, nuclear physics, string theory, etc., etc.

Quantum mechanics explains laboratory observations in these areas, often predicting the data correctly to many decimal places.

Most of non-quantum physics (classical mechanics, electrodynamics, classical waves and optics, classical thermodynamics) was invented prior to the 20th century. Einstein’s theories of special and general relativity are the main exception to this rule. They are a mayor piece of non-quantum physics invented in the 20th century. Special relativity and quantum mechanics were merged long ago (into what we now call relativistic quantum field theory), but we still don’t fully understand how to merge general relativity and quantum mechanics. We believe that this is possible and that even general relativity will eventually be assimilated by the Borg of quantum mechanics.

Shannon’s information theory (SIT) is amazing for its generality, and because it was born almost fully mature, in a single, remarkable 1948 paper by Claude Shannon. SIT has so far been used mostly in communication, coding and error correction theory. It has had some impact on physics, but I think it is fair to describe that impact as minor. So minor that SIT is rarely taught in physics courses (undergraduate or graduate). The main reason for this is, I believe, because, as Feynman once reminded us, “nature isn’t classical, dammit. And if you want to make a simulation of nature, you’d better make it quantum mechanical”. Since the original SIT is classical, it is not totally unexpected that its impact on physics has been minor so far.

But the game has now changed. In the past 20 years, remarkable advances have been made in the quantum version of SIT (Shannon Information Theory). I think quantum SIT is revolutionizing how quantum mechanics is used and understood. I fully expect that quantum SIT will become, in the near future, part of the standard physics curriculum. It may even some day play a nontrivial role in solving the puzzle of quantum gravity and string theory. It has already been used to elucidate the escape of information from a black hole.

To understand quantum SIT, you will first need to understand classical SIT. In my opinion, the following two books are excellent and they complement each other well:

  • David MacKay’s “Information Theory, Inference, and Learning Algorithms”. This book is available for free in pdf form, although it is well worth purchasing in paper form. (David’s website here)
  • Cover and Thomas’s “Elements of Information Theory, 2nd Edition (2006)”. A very well written classic. Amazon link here.

You only need to learn the basics of classical SIT before plunging into quantum SIT. These 2 books contain much more than the basics, so it is not necessary or even advisable to try to absorb them initially in their entirety. Furthermore, note that many pedagogical expositions of quantum SIT start with a brief review of classical SIT.

The pedagogical expositions of quantum SIT that are currently available are all still very new and not as polished as the Cover&Thomas and MacKay books. I found the following lectures very helpful.

I also like this master thesis by Ivan Savov (currently a PhD candidate under Patrick Hayden). Of course, you should also look at some of the original papers in ArXiv.

The latest craze in the quantum SIT community are the so called “resource inequalities”, invented by Devetak, Harrow and Winter. I’ve just started learning about them. I don’t fully understand them yet, but they appear to be a very deep result that ties together much previous work. They look like this: \alpha[c\rightarrow c] + \beta[q\rightarrow q] + \gamma[qq] \geq 0, where \alpha,\beta,\gamma are real numbers and

  • [c\rightarrow c]= one use of a noiseless c-bit (classical bit) channel
  • [q\rightarrow q]= one use of a noiseless q-bit (quantum bit) channel
  • [qq]= one e-bit (entanglement bit) shared between two parties (Alice and Bob)

These inequalities apply only in the limit of a large number of copies of the resource. Exploring such a limit is typical of what is done in SIT theories. Devetak, Harrow and Winter have proven their inequalities in a mathematically rigorous way.

Some questions to ponder:

  • What are the best applications of quantum SIT?

  • What does quantum SIT tell us about quantum computation? Can quantum SIT be reduced to simple statements about qubit circuits and quantum computer programs?

I’m not sure what are the best answers to these questions. Those answers will probably evolve as this young field continues to grow.

January 2, 2011

My Prediction for 2011- The Islamic Quantum Computer

Filed under: Uncategorized — rrtucci @ 11:00 am

Most predictions of the future are overly bland or biased or uninformed, or unrealistic. There is no reason to believe this one is any different, but one can hope.

I predict that some forward looking person from an Islamic country (similar to the Ansari family of X-prize fame, who are of Persian origin) will start a program to build a quantum computer. The program will FAR surpass its competitors in less than ten years. This, I believe, could be accomplished if the benefactors of the program install some very wise leaders to oversee the program.

According to this article written by someone called Huda:

“The Qur’an calls upon Muslims to look around them and study the physical world, so that they might appreciate the majesty of Allah’s creation”.

During the Middle Ages (particularly in the 7th-13th centuries C.E.), Islamic science was the best in the world, much better than anything in Europe or anywhere else. During that time, Muslims made significant inventions and discoveries in medicine, astronomy, mathematics, geography, chemistry, botany, and physics. In physics, for example, they discovered the law of conservation of momentum and Snell’s law. Latin translations from the original Arabic of the writings of the Persian Al-khwarizmi (780- 850 C.E.) brought to Europe for the first time the so called “Arabic” number system (first invented in India) that is universally used today. Prior to that, Europeans had been using the cumbersome Roman numeral system for commerce and accounting. According to Huda:

These English words are rooted in the Arabic language, demonstrating the influence of Muslim scholars in these fields:
• alchemy
• algebra
• algorithm
• alkali
• almanac
• antimony
• average
• azimuth
• camphor
• carat
• cipher (zero)
• elixir
• nadir
• pancreas
• zenith
• zircon

Abdus Salam (1926-1996), a Pakistani in love with his country and a devout Muslim of the Ahmadiyya sect, won (together with Sheldon Glashow and Steven Weinberg) the 1979 Physics Nobel prize. Salam was the first Muslim to win the prize.

About 20% of the world’s population is Muslim.

Blog at WordPress.com.

%d bloggers like this: