Site moved to, redirecting in 1 second...

2 posts categorized "Quantum Computing"

September 25, 2013

Are Space and Time Real?

"Physicists have discovered a jewel-like geometric object that dramatically simplifies calculations of particle interactions and challenges the notion that space and time are fundamental components of reality," writes Natalie Wolchover. ["A Jewel at the Heart of Quantum Physics," Quanta Magazine, 17 September 2013] Although that sounds far-fetched to the average person, there are few things about the wacky world of quantum physics that don't boggle the mind. The jewel-like shape at the heart of this new revelation is called an "amplituhedron" and it may be the key to unifying theories at the macro and micro levels. Wolchover continues:

"The revelation that particle interactions, the most basic events in nature, may be consequences of geometry significantly advances a decades-long effort to reformulate quantum field theory, the body of laws describing elementary particles and their interactions. Interactions that were previously calculated with mathematical formulas thousands of terms long can now be described by computing the volume of the corresponding jewel-like 'amplituhedron,' which yields an equivalent one-term expression."

This subject caught my eye because I recently read James Gleick's wonderful biography of Richard Feynman entitled Genius. By anyone's definition, Feynman, a Nobel Prize laureate, was a mathematical genius with a particular gift for being able to visualize the quantum world. Gleick called him "the most brilliant, iconoclastic, and influential physicist of modern times." One of the challenges with which Feynman wrestled was the paradox that particles simultaneously behave as particles and waves. That makes any attempt to determine where a particular particle is at a particular time very problematic. Gleick's narrative about Feynman's contribution to the subject at hand also explains why the new geometric shape is called an amplituhedron:

"[Feynman] developed an alternative formulation of quantum mechanics to add to the pair of formulations produced two decades before by [Erwin] Schrödinger and [Werner] Heisenberg. He defined the notion of a probability amplitude for a space-time path. In the classical world one could merely add probabilities: a batter's on-base percentage is the 30 percent probability of a base hit plus the 10 percent probability of a base on balls plus the 5 percent probability of an error ... In the quantum world probabilities were expressed as complex numbers, numbers with both a quantity and a phase, and these so-called amplitudes were squared to produce a probability. This was the mathematical procedure necessary to capture the wavelike aspects of particle behavior. ... Probability amplitudes were normally associated with the likelihood of a particle's arriving at a certain place at a certain time. Feynman said he would associate the probability amplitude 'with an entire motion of a particle' — with a path. He stated the central principle of his quantum mechanics: The probability of an event which can happen in several different ways is the absolute square of the sum of complex contributions, one from each alternative way. These complex numbers, these amplitudes, were written in terms of classical action; he showed how to calculate the action for each path as a certain integral. And he established that this peculiar approach was mathematically equivalent to the standard Schrödinger wave function, so different in spirit. ... [Using Feynman's ideas,] Polish mathematician Mark Kac ... created a new formula, the Feynman-Kac Formula, that became one of the most ubiquitous of mathematical tools, linking the applications of probability and quantum mechanics. ... Feynman's path-integral view of nature, his vision of a 'sum over histories,' was also the principle of least action, the principle of least time, reborn."

Commenting on the discovery of the amplituhedron, Robert T. Gonzalez writes, "In the past, Feynman diagrams (which are themselves very powerful and elegant simplifying tools) didn't help us in understanding some specific particle interactions because the number of terms that needed to be calculated were so huge that even our most powerful supercomputers couldn't crack a solution." [See "Comments" at the end of his post entitled "This physical breakthrough could change our understanding of spacetime," io9, 20 September 2013] I suspect Feynman would have been thrilled with the new discovery. Wolchover's article in Quanta Magazine was accompanied by artist Andy Gilmore's rendition of what the amplituhedron looks like.


Continuing her superb article about why the discovery of the amplituhedron is so important, Wolchover writes:

"The new geometric version of quantum field theory could also facilitate the search for a theory of quantum gravity that would seamlessly connect the large- and small-scale pictures of the universe. Attempts thus far to incorporate gravity into the laws of physics at the quantum scale have run up against nonsensical infinities and deep paradoxes. The amplituhedron, or a similar geometric object, could help by removing two deeply rooted principles of physics: locality and unitarity. ... Locality is the notion that particles can interact only from adjoining positions in space and time. And unitarity holds that the probabilities of all possible outcomes of a quantum mechanical interaction must add up to one. The concepts are the central pillars of quantum field theory in its original form, but in certain situations involving gravity, both break down, suggesting neither is a fundamental aspect of nature. In keeping with this idea, the new geometric approach to particle interactions removes locality and unitarity from its starting assumptions. The amplituhedron is not built out of space-time and probabilities; these properties merely arise as consequences of the jewel’s geometry. The usual picture of space and time, and particles moving around in them, is a construct."

Scott Aaronson, a theoretical computer scientist and faculty member in the Electrical Engineering and Computer Science department at the Massachusetts Institute of Technology, suspects that there will be a lot of skeptics about the claim that the amplituhedron will "be a 'jewel' that unlocks all of physics, or a death-knell for spacetime, locality, and unitarity." After all, he notes, it applies to a "restricted class of theories." Aaronson himself may be a skeptic; nevertheless, he asserts tongue in cheek and writes, "If anything, the popular articles have understated the revolutionary importance of the amplituhedron. And the reason I can tell you that with such certainty is that, for several years, my colleagues and I have been investigating a mathematical structure that contains the amplituhedron, yet is even richer and more remarkable. I call this structure the 'unitarihedron'." ["The Unitarihedron: The Jewel at the Heart of Quantum Computing," Shtetl-Optimized, 20 September 2013] Aaronson goes on to explain:

"The unitarihedron encompasses, within a single abstract 'jewel,' all the computations that can ever be feasibly performed by means of unitary transformations, the central operation in quantum mechanics (hence the name). Mathematically, the unitarihedron is an infinite discrete space: more precisely, it's an infinite collection of infinite sets, which collection can be organized (as can every set that it contains!) in a recursive, fractal structure. Remarkably, each and every specific problem that quantum computers can solve — such as factoring large integers, discrete logarithms, and more — occurs as just a single element, or 'facet' if you will, of this vast infinite jewel. By studying these facets, my colleagues and I have slowly pieced together a tentative picture of the elusive unitarihedron itself. One of our greatest discoveries has been that the unitarihedron exhibits an astonishing degree of uniqueness. At first glance, different ways of building quantum computers — such as gate-based QC, adiabatic QC, topological QC, and measurement-based QC — might seem totally disconnected from each other. But today we know that all of those ways, and many others, are merely different 'projections' of the same mysterious unitarihedron."

Aaronson good humoredly reports that he is "awestruck" by "mathematical elegance and power" of the unitarihedron. He continues:

"But I haven’t even told you the most spectacular part of the story yet. While, to my knowledge, this hasn’t yet been rigorously proved, many lines of evidence support the hypothesis that the unitarihedron must encompass the amplituhedron as a special case. If so, then the amplituhedron could be seen as just a single sparkle on an infinitely greater jewel. Now, in the interest of full disclosure, I should tell you that the unitarihedron is what used to be known as the complexity class BQP (Bounded-Error Quantum Polynomial-Time). However, just like the Chinese gooseberry was successfully rebranded in the 1950s as the kiwifruit, and the Patagonian toothfish as the Chilean sea bass, so with this post, I'm hereby rebranding BQP as the unitarihedron. For I've realized that, when it comes to bowling over laypeople, inscrutable complexity class acronyms are death — but the suffix '-hedron' is golden."

In addition to his intellect, Aaronson obviously possesses a good sense of humor. Luboš Motl, however, isn't amused. "The amplituhedron exists," he writes, "while the diaperhedron or any other computer-science-based objects Aaronson talks about don't exist as objects." ["Diaperhedron can't match amplituhedron," The Reference Frame, 21 September 2013] Wolchover concludes her article by writing:

"Beyond making calculations easier or possibly leading the way to quantum gravity, the discovery of the amplituhedron could cause an even more profound shift, [Nima Arkani-Hamed, a professor at the Institute for Advanced Study,] said. That is, giving up space and time as fundamental constituents of nature and figuring out how the Big Bang and cosmological evolution of the universe arose out of pure geometry. 'In a sense, we would see that change arises from the structure of the object,' he said. 'But it's not from the object changing. The object is basically timeless.' While more work is needed, many theoretical physicists are paying close attention to the new ideas."

Admittedly the subject of quantum physics is difficult to grasp. Wolchover does a remarkable job of making it accessible to everyone. I highly recommend that you read her entire article.

September 18, 2013

Understanding Quantum Computing

Let's face it quantum computing is not an easy subject. Understanding, for example, that a qubit can simultaneously represent both a 0 and 1 and that it would only take 300 qubits to hold all of the data that has ever been created since the big bang takes a little mind bending. In previous posts about quantum computing, I've noted that scientists have argued about whether the computer designed and marketed by D-Wave is a quantum computer. You would think that such a thing would be easy to determine; but you would be wrong. Erica Klarreich explains:

Qubit"In early May, news reports gushed that a quantum computation device had for the first time outperformed classical computers, solving certain problems thousands of times faster. The media coverage sent ripples of excitement through the technology community. A full-on quantum computer, if ever built, would revolutionize large swaths of computer science, running many algorithms dramatically faster, including one that could crack most encryption protocols in use today. Over the following weeks, however, a vigorous controversy surfaced among quantum computation researchers. Experts argued over whether the device, created by D-Wave Systems, in Burnaby, British Columbia, really offers the claimed speedups, whether it works the way the company thinks it does, and even whether it is really harnessing the counterintuitive weirdness of quantum physics, which governs the world of elementary particles such as electrons and photons. Most researchers have no access to D-Wave's proprietary system, so they can't simply examine its specifications to verify the company's claims. But even if they could look under its hood, how would they know it's the real thing? Verifying the processes of an ordinary computer is easy, in principle: At each step of a computation, you can examine its internal state — some series of 0s and 1s — to make sure it is carrying out the steps it claims. A quantum computer's internal state, however, is made of 'qubits' — a mixture (or 'superposition') of 0 and 1 at the same time, like Schrödinger’s fabled quantum mechanical cat, which is simultaneously alive and dead. Writing down the internal state of a large quantum computer would require an impossibly large number of parameters. The state of a system containing 1,000 qubits, for example, could need more parameters than the estimated number of particles in the universe. And there's an even more fundamental obstacle: Measuring a quantum system 'collapses' it into a single classical state instead of a superposition of many states." ["Is That Quantum Computer for Real? There May Finally Be a Test," Wired, 23 August 2013]

Before continuing the discussion about the difficulty of determining whether a machine is a quantum computer or not, you should watch the following video. As Mike James reports, "This animation ... might give you some idea as to why quantum computers are more powerful - or potentially more powerful - than a classical computer." ["Quantum Computers Animated," I Programmer, 25 August 2013] As terrific as the animation is, James warns that you are still likely "to be mystified. Quantum computers are difficult to understand because they rely on the mathematics of quantum mechanics and most people don't understand the math."

If you watched the video, then it will be easier for you understand what James writes next:

"It is too easy to say that the reason a quantum computer is more powerful is that a qubit, or quantum bit, can represent a zero and a one at the same time. This seems like a powerful idea, but it doesn't really give you much that is new in terms of computation. It is only when you allow a set of qubits to be entangled do you get really new behavior. When qubits are entangled the result of one measurement affects another and you can use it for encryption and computation. The big problem is that entangled states are corrupted by any interactions with the outside world - a problem known as decoherence. So far this has made building quantum computers with more than a small number of qubits difficult."

Eric Limer adds, "Someday, somehow, quantum computing is going to change the world as we know it. Even the lamest quantum computer is orders of magnitude more powerful than anything we could ever make today. But figuring out how to program one is ridiculously hard." ["Why Programming a Quantum Computer Is So Damn Hard," Gizmodo, 23 August 2013] Jeremy O'Brien, a professor at the University of Bristol, agrees with Limer about how difficult it is to code for a quantum computer. "A quantum computer can do things faster for you, but someone has to program it," he states, "and at the moment there are only a handful of people around the world who would be qualified." If that situation remains, he and colleagues know that it will mean that there will be "a dearth of skilled coders when the expected quantum revolution finally arrives." To remedy that situation, they are making available to "anyone with a web browser" a quantum chip capable running basic algorithms over the internet. ["Quantum chip connected to internet is yours to command," NewScientist, 6 September 2013]

Limer's claim that quantum computing is "going to change the world" leaves the impression that there is something magical about a quantum computer. James reminds us, however:

"A quantum computer cannot compute anything that a classical computer cannot. Indeed the operation of a quantum computer can be simulated by a classical computer, but it might take longer than the lifetime of the universe to complete the job. Quantum computers promise fast solutions nothing more."

That's really the point. Quantum computers will allow us to make computations that, for all practical purposes, are currently impossible. Will this change the world? Possibly. James points out that D-Wave's machine is "a quantum annealing device which can be used to solve specific optimization problems. It is more like a quantum analog computer than anything else." That's been part of the controversy and brings us back to Klarreich's article about trying to figure out if a computer is really quantum computer. She writes:

"It turns out ... that there is a way to probe the rich inner life of a quantum computer using only classical measurements, if the computer has two separate 'entangled' components. In the April 25 issue of the journal Nature, [Umesh Vazirani of the University of California, Berkeley], together with Ben Reichardt of the University of Southern California in Los Angeles and Falk Unger of Knight Capital Group Inc. in Santa Clara, showed how to establish the precise inner state of such a computer using a favorite tactic from TV police shows: Interrogate the two components in separate rooms, so to speak, and check whether their stories are consistent. If the two halves of the computer answer a particular series of questions successfully, the interrogator can not only figure out their internal state and the measurements they are doing, but also issue instructions that will force the two halves to jointly carry out any quantum computation she wishes. 'It's a huge achievement,' said Stefano Pironio, of the Université Libre de Bruxelles in Belgium. The finding will not shed light on the D-Wave computer, which is constructed along very different principles, and it may be decades before a computer along the lines of the Nature paper — or indeed any fully quantum computer — can be built. But the result is an important proof of principle, said Thomas Vidick, who recently completed his post-doctoral research at the Massachusetts Institute of Technology. 'It’s a big conceptual step.'"

Klarreich's article contains a lot more interesting information about the quirkiness of quantum physics and you should check it out. Researchers are continuing to make breakthroughs in the area of quantum computing; but, no one has any idea when a true quantum computer (i.e., one that can be confirmed by the interrogation test) will be built.