Quantum Simulation of the Factorization Problem | Hacker News Reader

Quantum Simulation of the Factorization Problem

arxiv.org

50 pointsCarolineW6 comments

Here's a explanation for laymen of what this means: http://phys.org/news/2016-11-quantum-physics-factor.html

Some excerpts:

The researchers have shown that the arithmetic used in factoring numbers into their prime factors can be translated into the physics of a device—a "quantum simulator"—that physically mimics the arithmetic rather than trying to directly calculate a solution like a computer does.

For now, the researchers do not know the technical complexity of building such a device, or whether it would even be possible to factor very large numbers.

"We have shown that a quantum simulator able to factor numbers exists and, in principle, it could be built," Martin said. "Whether the simulator is feasible with current technology in a way that it can factor numbers of the same size as the ones used in cryptography remains to be seen, but the avenue is now open. The prospect of building such a device before a quantum computer is built is something to be pondered seriously."

One of the most mathematically interesting aspects of the new work is that it involves redefining the factorization problem by introducing a new arithmetic function that could then be mapped onto the physics of the quantum simulator and correspond to the energy values. In a sense, the researchers are rewriting the math problem in terms of physics.

"The manuscript tries to bridge number theory with quantum physics," Rosales said, noting that researchers have been trying to do this for several decades. "Nowadays with the development of quantum information and computation and the discovery of Shor's algorithm, the connection seems more intriguing and important than ever."

I still don't quite understand:

"The method is 'analogue' in the sense that it is not like Shor's algorithm, which is programmable in a quantum computer following the gate model. Instead, it is the measurement of a carefully set quantum system that provides the answer."

Isn't the gate model _also_ a carefully set quantum system, the measurement of which provides the answer? Can someone shed some light on this please?

As a rough way to understand this, take a look at the difference in operation between an analog computer [0] and a digital computer. One of the main differences is that an analog computer does not achieve a given "operation" (e.g. integration of an input function) via a discrete heurestic (i.e. by executing the calculation in steps using say numerical integration), but rather the analog computer embodies the operation itself via its underlying physics.

Essentially, these researchers have proposed a way to tackle integer factorization by creating a quantum system that embodies the calculation itself, rather than performing discrete steps on an input to find its factors as one would via, say, Shor's Algorithm on a "general-purpose" quantum computer.

As is mentioned in GP post's link, this is potentially a significant result in both pure math (quantum number theory) and applied cryptography.

[0] https://en.wikipedia.org/wiki/Analog_computer

Imagine creating a device to keep track of time. A couple of ways to do this are:

1). Use a programmable computer to write code

2). Place a gnomon on a flat plate to make a sundial

The first way is the gate model, it's algorithmic, like Shor's algorithm.

The second way is analog. There is no algorithm. The solution consists of simply measuring a shadow.

Wow this is a huge deal. They devised a way to solve hard math problems (large number factorization) with physics itself, and were able to validate it against novel factorization algorithms. Mapping number theory to quantum physics is no small feat. Really stretches what we think of when we say "computing" an answer to a problem.

When you say solve problems using "physics itself", I think it's important to clarify it's quantum physics.

Mapping math problems to classical physics has been done for quite a while, for example http://www.nutsvolts.com/magazine/article/analog_mathematics.

Reply on news.ycombinator.com