Disentangling the Spooky Quantum Puzzle

Daniel Lidar, Sloan Fellow ’93, is in his office struggling to explain his work in quantum computing. Concepts that are clear in the equations don’t fit into words. When asked if there is a metaphor, something to compare it to that people would understand, he pauses, thinks and shakes his head, no.

The discussion is not academic. The concepts may be hard to express in words, but their promise is clear. Quantum computing is emerging as the key to the next generation of machines, and a diverse group of USC researchers, most of them from the Viterbi School’s newly named USC Ming Hsieh Department of Electrical Engineering, is beginning the second century of USC engineering with a strong bid for pre-eminence in the new field.

"Computer chips have been doubling in density every year or so, following the well-known “Moore’s Law” that has been the engine of the information era," Lidar wrote in the prospectus for a new research unit, the USC Center for Quantum Information Science and Technology. "Unfortunately, this will soon end, as individual electronic components shrink to the atomic scale in the coming 10-20 years. This is exactly the domain where the mysterious and fantastic laws of quantum physics take center stage."

"The current challenge in the field," Lidar continued, "is to realize hardware that behaves almost purely quantum-mechanically, discover new ways to organize and operate such quantum resources, and develop new algorithms and applications of this future information processing capability."

This challenge is as challenging as challenges get. The "hardware" consists of individual atoms, molecules and photons. At this atomic scale, matter behaves according to the rules of quantum mechanics.

And these rules are deeply counter-intuitive and ineradicably strange: "For instance,” Lidar continues, “quantum bits (qubits) can maintain both state 0 and 1 simultaneously, and when many qubits are considered together, they allow unparalleled storage capacity. Consider that with merely 300 atoms, the resulting memory is more than could be possible even if every atom in the universe were part of a conventional computer.”

"The outstanding feature of a quantum information processor is entanglement, what Einstein termed 'spooky action-at-a-distance.' Entanglement is a subtle and strange concept, and it is not even clear how to quantify entanglement for more than a few qubits."

As one observer commented seeing similar evidence, “we're not in Kansas anymore.”

Beyond Human Intuition

While the mathematical theory is well established, that's only a beginning. The design of real-world working devices by engineers has traditionally relied in substantial measure on human intuition, on a feeling for what is happening in fluid flows, computer circuits, metallic behavior, and other realms. Humans look for and find patterns and symmetries that suggest approaches. But at the quantum level symmetry can mislead, the pattern is no pattern, and very little human experience is of any use.

Viterbi engineers are finding ways to negotiate this strange terrain. The English-born Anthony F. J. Levi, who came to USC as a full professor of electrical engineering at the age of 34 in 1993 from Bell Labs, has been focusing explicitly on the mismatch of human experience with the quantum world for the past six years.

“You have a vast array of alternative ways to do the same thing at this level,” he says. “Nanoscience gives you too many degrees of freedom. Human minds work by looking for symmetry, by identifying patterns. But in nature, you can often get better performance by breaking symmetry."

Levi has an introduction to his method, including some test examples, on his Quantum Engineering web pages. http://www.usc.edu/aleviIt is dramatic break from classic chip design methodology, which he says has proceeded in what he calls an ad-hoc manner— a seat-of-the-pants intuitive process, which follows what's worked satisfactorily before, without ever considering that something entirely different might work better.

While human minds can't deal with 20 or 50 degrees of freedom, appropriately constructed computer searches can, says Levi. "You input a physical model that embodies the behavior of the system. That behavior is controlled with parameters, as many as 50 or 100. The machine then tries to change the parameters to find an optimal response."

Levi and Stephan Haas, a professor of physics and astronomy in the USC College, are using this design process to create new species of multi-layered semiconductor devices, "varying the semiconductor composition throughout the material, layer by layer." Two more professors of mathematics from the College, Chunming Wand and Gary Rosen are also part of the team.

The resulting devices literally defy human understanding. "You can't make sense of it by looking at it," he says. But it works.

And the design tools themselves, as they evolve, carry the knowledge, not their human users. "It used to be," says Levi, "that people die, but their knowledge was recorded in books. Now, it's in the tools. You encode what you learn into the design tool."

Quantum Circuits

Levi's efforts are part of a broad effort in the Hsieh Department. Other researchers are addressing the issue of creating quantum circuits that can be used to solve real problems. Humans may not be able to intuit exactly how quantum level physical structures work, but they must be able to visualize the circuits in order to design them. And for this, Massoud Pedram, a Hsieh Department NSF PECASE (Presidential Early Career Award for Scientists and Engineers) winner, recently found a method that has the potential to drastically simplify the process.

"The key milestone achieved so far is the … development of a canonical and concise representation of quantum logic circuits in the form of quantum decision diagrams (QDD’s)," says Pedram. These diagrams allow engineers to visualize information flows through the system — that is, to apply the expertise they have in silicon circuit design to the quantum world, accurately and rigorously.

"Preliminary experimental results show that the QDD-based functional decomposition approach speeds up the synthesis of quantum logic circuits by orders of magnitude compared to the best known quantum synthesis techniques"

Pedram's is not the only recent USC breakthrough. At the far theoretical end, Lidar has just developed a new way to use Einstein spookiness to drastically speed up the process of debugging a new quantum computer design - a critical step in which all possible inputs are put in, to see the range of observed outputs.

Lidar created the method with his former grad student Masoud Mohseni (now at Harvard). “Through the strange features of entanglement, the correlation between the two qubits at the output contains more information than if an unentangled qubit were fed to the machine. Thus each time when a qubit pair is measured at the output, a bit more information is gained than would be possible classically.” The bottom line is that quantum debugging looks possible using a fraction of the trials that would be necessary for a conventional, electronic design.

Other Hsieh Department theorists are also quantum standouts. In fall 2006, Todd Brun and Igor Devetak published a paper in Science on a major advance in error correction coding for quantum computing.

Error correction coding is a fundamental process that underlies all of information science, but the task of adapting classical error correction codes to quantum computing has long bumped up against an apparently fundamental limitation.

Irving Reed, a USC emeritus professor and National Academy of Engineering member was co-creator of one of the most widely used of these codes, the Reed-Solomon codes. Those error-correcting codes make possible error free sound emanating from scratched compact disks and clear faxes sent through less than perfect telephone circuits. Reed discusses their importance to computer science and electronics in general in his 2005 memoir, Alaska to Algorithms.

"The human mind is capable by the use of context and language redundancy to intuitively perform error-correction," he writes. "But electronic equipment is extremely fussy: it demands a perfection that isn't found in the noisy real world. Error coding permits these fastidious machines to function as part of real world systems, in real time."

Brun says quantum computing systems processing quantum data as qubits carried on single photons, are even more fastidious than electronic ones making error codes even more necessary. But the peculiar physical laws governing quantum messages have long created a problem. The process of decoding the most efficient error codes to look for "error syndromes"—tell-tale signals that indicate an error has been detected and is being corrected—creates new interference errors.

Brun, Devetak and graduate student Min-Hsiu Hsieh found that adding a dose of entangled qubits to the message resolved the paradox and allowed the use of ultra-efficient turbo codes, a step whose importance was signaled in Science by an interpretive article accompanying the paper.

USC quantum fingerprints

Quantum computing is still in its cradle. But the very first useful devices are starting to emerge in the field of cryptography, Lidar says. In this area, the "spooky" entanglement feature provides a remarkable benefit. It is not just that the message is encrypted using advanced high-security techniques. It is that any attempt to read the message by anyone is immediately detected.

Actual quantum computing devices are still far away, But USC, because its faculty is rich in exactly the expertise needed for this daunting challenge, is riding the crest of first quantum research wave.

In Lidar's proposal for the Center for Quantum Information Science and Technology (CQIST), he notes " the unique strength of the University of Southern California" in the necessary skills and says: "When quantum information devices are ultimately realized, they will have University of Southern California fingerprints."

The Lidar proposal identifies 10 faculty members for the center, including fiber optics specialist and PECASE winner Alan Willner and Stephen Cronin from the Viterbi School in addition to Levi, Brun, and Devetak, plus physicists Hans Bozler, Jia Grace Lu and Paolo Zanardi.

And the web already extends further. John O'Brien, another PECASE winner who recently became Viterbi’s Senior Associate Dean for Academic Affairs, is the lead investigator on an NSF-funded $1.3 million Nanoscale Interdisciplinary Research Team (NIRT) project to build a device that will carry signals on individually generated and controlled single photons, one after another, each one generated by a single electron.

The effort involves work by Levi, Brun, and Willner, plus signals specialist William Lindsey and optical device expert P. Dan Dapkus, all of them faculty in the Hsieh Department.

"This is an ambitious project that requires an exceptionally broad range of expertise in numerous electrical engineering disciplines," commented Viterbi School Dean Yannis Yortsos. "Swift success in a project this bold is never guaranteed, but I am extremely proud we have been able to assemble an in-house team that has the background to even attempt it."

--by Eric Mankin