Friday, May 18, 2018

Physicists Introduce "Quantum Fraud" Detection Tests

It’s hard enough to identify a knockoff Louis Vuitton bag. When quantum computers hit the market, how will buyers know they’re not getting duped...or settling for something that isn’t quite as “quantum” as they think?

Image Credit: Luana Azevedo.
Francesco Buscemi, a physicist in the Department of Mathematical Informatics at Nagoya University in Japan, phrases the question this way, “As more and more models of new quantum computers become commercially available, can we actually certify that the black-box we just bought is able to perform genuine quantum operations and not just running some classical simulation? Or should we just trust the sticker ‘Quantum Inside’ affixed to its casing?”

This isn’t just a hypothetical question. Scientists have made great strides in the field of quantum computing over the last few years, moving from the “we think it’s possible” stage to creating real working quantum computers. No quantum computer can outperform the device on which you’re reading this article yet, but that day is coming—and it’s coming soon. To prepare for this, Buscemi and colleagues Denis Rosset and Yeong-Cherng Liang at National Cheng Kung University in Taiwan recently outlined a set of tests that computers with quantum-based memory can pass, but classical imposters will fail. This new research was published last week in the American Physical Society’s journal Physical Review X.

Classical computers use bits to store information. Each bit can be in one of two states: 1 or 0. Quantum computers use qubits (the name comes from quantum and bit) to store information. Each qubit can store information as a 1, 0, or any superposition of the two numbers—meaning that it can act something like both a 1 and 0 at the same time. Things get even stranger though; qubits can experience quantum entanglement. This means that the state of one qubit can depend on the state of another qubit, even if the two are separated by a long distance, in a way that can’t be explained by classical theory.

This quantum strangeness gives quantum computing its power. Qubit-based computers will be able to seriously outperform classical computers in some really important areas, although they aren’t likely to be personal computers. “What is clear now is that quantum computers will never entirely replace classical ones, which will probably remain the most versatile machines to interact with (for us humans, at least),” says Buscemi. “What quantum computers will do is to help classical computers solve some specific—though practically relevant—problems,” he says.

If factoring prime numbers and simulating the behavior of atoms don’t sound like practically relevant problems, consider this: Without breaking a sweat, a quantum computer could break the encryption system that protects your online financial transactions. The factoring of prime numbers forms the basis of many top-notch cryptography systems; that’s one of the reasons big-budget companies and governments have invested heavily in this area. On the other hand, quantum computing offers the lure of an unbreakable encryption system based on quantum entanglement.

As for simulating particle interactions, that’s where things get even more exciting. Classical computers can’t model chemical and molecular interactions in very much detail—the interactions are just too complicated. This kind of simulation, though, could shed tremendous insight on the causes of medical conditions, as well as prevention and treatment methods. It could help us design new medications and materials ideally suited for specific applications. All kinds of doors would open with a more complete understanding of these interactions.

Before we get too carried away by the possibilities of quantum computing, let’s return to the question at hand—how can you distinguish between a real quantum computer and an imposter?

Any computer, quantum or classical, must be able to receive, store, process, and output information. The key to the power of a quantum computer is in the quantum nature of the qubits that store information. But that’s also where imposters can sneak in. Classical computers can receive quantum inputs, measure them, store the measured value classically, process the stored information, and output information. This sounds quantum-y, but measuring the quantum input breaks its entanglement. In other words, it destroys the quantum nature of your input—and with it your quantum advantage.

Francesco Buscemi explains quantum computing “imposters” to his students.
Image Credit: Wenbin Zhou
Differentiating between a real quantum computer and an impostor is tricky business. There are several approaches to quantum computers, including qubits based on properties of electrons, quantum dots, photons, and other things. It’s clear that there won’t be one “standard” quantum computer, says Buscemi. He explains, “In short, the landscape of quantum computing is evolving into something extremely rich and varied, in which no single machine will outperform all the others in any given task. The challenge is to keep such a wonderful garden under control, preventing it from turning into an inextricable jungle.”

That’s the motivation of this new research, to help preserve the garden but prevent the jungle. The first step in developing these benchmarks for quantumness was to demonstrate that they actually exist. So, using an approach rooted in statistical decision theory, the team showed that there is a class of tests that can differentiate between a computer memory that stores information classically and one that preserves the quantum-ness of the input. The tests work for all different kinds of quantum computers.

Next, the researchers constructed the tests. They did so by identifying a set of quantum input signals that contain signature correlations. These inputs and outputs reveal whether the signals were stored by a quantum or classical memory system. The tests are all-encompassing—real quantum computers will always pass and imposters will always fail—and they are also experimentally feasible. As if to demonstrate that they shouldn’t be discredited, regular old computers played an important role in designing the practical tests. “Ironically, classical computers turn out to be very useful in designing the benchmarks they cannot pass,” Buscemi noted.

Quantum computers aren’t far enough along for vendors to start printing “Quantum Inside” stickers or for scientists to run such verification tests, but we are moving ever closer to quantum supremacy, the Hollywood-sounding name for when quantum computers begin outperforming classical computers on the relevant kinds of problems. In the meantime, can someone create an all-encompassing test for identifying knockoffs based on eBay listings?

—Kendra Redmond

1 comment:

  1. "Factoring of prime numbers" is a common solecism. I am, however, interested in whether anyone has compiled data on the success probabilities achievable by classical ways to "fake" Shor's algorithm. Random guess of an a < N and doing gcd(a,N) obviously succeeds with probablilty 1 - totient(N)/N ~= 1/sqrt(N), but how about (a) random trials of the fractional-approximation end-stage or (b) collapsing more of the state ebfore applying QFT?

    ReplyDelete