QuICS Hosts Five-Day Workshop on Quantum Complexity Quandary

August 8, 2016

Three postdoctoral fellows in the Joint Center for Quantum Information and Computer Science (QuICS) recently led a workshop to tackle a demanding problem in quantum complexity theory, the field that studies how much memory or time quantum computers need to solve problems or check their answers.

The five-day workshop, from Aug. 1 – 5, focused on a connection between quantum entanglement—the bizarre feature of microscopic physics that can link two widely separated atoms or electrons—and a particular quantum complexity class.

That class is known as QMA(2), the collection of problems for which a quantum computer can quickly check that an answer is right—as long as it’s also given two unentangled quantum states.

“We wanted to have a workshop with an extremely focused topic, bring together the experts in this area and hopefully make progress on this challenging problem,” says Shelby Kimmel, a QuICS Hartree Fellow who helped organize the event with Cedric Lin (also a Hartree Fellow) and QuICS postdoctoral scholar Bill Fefferman.

Prior work on QMA(2) indicated that this group of problems might be larger than a similar collection without the restriction on entanglement, Kimmel says, which is odd given that the promise of unentanglement seems to give you extra computing power.

The workshop drew about a dozen outside experts to QuICS, along with another dozen local students and postdocs. Just seven formal talks peppered the weeklong schedule, which included many chances for both free discussion and more guided tutorials. Kimmel reports that no major breakthroughs have emerged yet, but attendees praised the format of the workshop and the educational discussions.

“I learned many things that I didn’t know before,” says Matthias Christandl, a math professor at the University of Copenhagen and a workshop attendee, “and I like the fact that it’s super focused.” Christandl adds that the workshop “has the advantage that people can talk to each other,” a contrast to academic conferences with a broader focus and attendees that have less technical language in common.

Those larger conferences are great for offering a sampling of the latest research, Kimmel says, but it is not always so helpful for making research progress. “We want to try something different,” she says. “This has been working out well, and the discussion periods have been really energetic. Hopefully we can host another workshop next year.”

QuICS is a partnership between the University of Maryland and the National Institute of Standards and Technology. It is one of 16 centers and labs in the University of Maryland Institute for Advanced Computer Studies.

—Story by Chris Cesare