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.
Although the researchers have not yet built a quantum simulator, they show that the prime factors of large numbers would correspond to the energy values of the simulator. Measuring the energy values would then give the solutions to a given factoring problem, suggesting that factoring large numbers into primes may not be as difficult as currently thought.
"The work opens a new avenue to factor numbers, but we do not yet know about its power," Rosales told Phys.org. "It is very striking to find a completely new way to factor that comes directly from quantum physics. It does not demonstrate that factoring numbers is easy, but finding new ways to factor certainly does not add to the strength of algorithms based on its assumed complexity."
(Score: -1, Spam) by Anonymous Coward on Monday November 28 2016, @10:05PM
(Score: 4, Insightful) by BsAtHome on Monday November 28 2016, @10:34PM
If the factoring problem can be solved this way, then there may be a new avenue open to NP vs P. That can result in a real problem for our current encryption tech. On the other hand, solving some graph theory problem in P time would be cool too.
(Score: 2, Interesting) by shrewdsheep on Tuesday November 29 2016, @09:33AM
Your first assertion is probably false. Prime factorization has at least not been proven to be NP-hard and it is suspected to be less complex. Your second assertion is true on the other hand: both ssh and https would fall with no implemented replacement at the moment, so that would have a huge impact. To my knowledge elliptic curve cryptography would not be dragged along, so that would be a potential alternative.
(Score: 2) by FatPhil on Tuesday November 29 2016, @11:38AM
However, the emphasis is on the "if", we really aren't making great steps maintaining a coherent quantum state of any real size at all such that the current crypto needs to be in fear of quantum computation.
Great minds discuss ideas; average minds discuss events; small minds discuss people; the smallest discuss themselves
(Score: 0, Insightful) by Anonymous Coward on Monday November 28 2016, @10:44PM
I call bullshit on this... something that hasn't been invented could be used by something that hasn't been invented to break something that works. Call me when they've turned it into something I can fund on Kickstarter.
(Score: 5, Informative) by AthanasiusKircher on Monday November 28 2016, @11:19PM
I call bullshit on this... something that hasn't been invented could be used by something that hasn't been invented to break something that works.
Well, quantum factoring IS already a thing -- using Shor's algorithm [wikipedia.org] and adiabatic quantum computation [wikipedia.org] have already been used to factor numbers as large as ~50,000.
The question isn't whether quantum computing can factor large numbers (and presumably break encryption) -- because it has already been demonstrated that it can be done on a small scale. The question is now an engineering one about how easily it can be scalable. I haven't looked into the details of TFA, but it's a different approach from the typical qubit computational model that seems intriguing.
Anyhow, sometimes figuring out the math or the physics is important before trying to build something. It may not be practical yet, but it's far from the actual BS I read in a lot of studies.
(Score: 1) by Francis on Tuesday November 29 2016, @03:28AM
It's an important precursor, but there's tons of things that work out fine in math, but aren't reasonable solutions when built. If they haven't even built a test unit for their design, then they haven't actually done any science and shouldn't have people think they have.
It is an important step and I'm sure the math was quite difficult, but they haven't shown what it would do, at best they've shown what it could do if their estimations are all correct.
(Score: 3, Informative) by FatPhil on Tuesday November 29 2016, @11:49AM
No, no, no, no, no, and six times no. It has factored a class of numbers, some of the members of the class are as large as tens of thousands. However, this class of numbers can be factored with *linear time* algorithms classically (which can also be called *constant time* algorithms with certain theoretical-but-not-practical assumptions about the computational model). You've fallen for the quantum computing world's "we are relevant, trust us" propaganda, which alas the popular scientific press likes to also propagate.
I can teach a parrot to say "97 and 101", but that doesn't mean it can factor numbers as large as ~10000.
Great minds discuss ideas; average minds discuss events; small minds discuss people; the smallest discuss themselves
(Score: 3, Insightful) by dingus on Tuesday November 29 2016, @04:35PM
This is accurate, and in fact even on wikipedia it says that the highest number factored with shor's algorithm is currently 21.
Still, the possibility of quantum computers breaking RSA and ECC is legitimate, and anyone hoping to keep their asymmetric communications secure for more than 15 years should definitely be looking into quantum-safe encryption schemes.
(Score: 2) by FatPhil on Wednesday November 30 2016, @01:26PM
(just remember to not copy the script, that breaks the laws of physics)
Great minds discuss ideas; average minds discuss events; small minds discuss people; the smallest discuss themselves
(Score: 2) by dyingtolive on Monday November 28 2016, @11:26PM
That can be explained by quantum mechanics too. Watch, I'll show how:
1. Accept that there is a full set of all possibilities for a given outcome to a situation.
2. (Magic)
3. You have the subset you were looking for!
Easy! :-)
Yeah, I don't get it either. I don't think I'm ready to be quite so dismissive about it though.
Don't blame me, I voted for moose wang!
(Score: 0) by Anonymous Coward on Monday November 28 2016, @11:58PM
What do you all think about using meta data as a metaphor.
This approach sets up a system, then instead of processing through the actual data it looks at the meta data of how the simulator is running. Analysis of the meta data shows us aggregate results that point to the answer.
(Score: 2, Informative) by Anonymous Coward on Tuesday November 29 2016, @03:44AM
Look up "analog computer" - an electrical circuit can be rigged up to model a specific algebraic formula and get almost instant evaluation/approximation.
(Score: 0) by Anonymous Coward on Tuesday November 29 2016, @05:57AM
Yes, but analog computers, unlike quantum ones, are no more powerful than digital computers.
(Score: 0) by Anonymous Coward on Tuesday November 29 2016, @08:21AM
uhm... it makes no sense to talk about the power of an analog computer.
think of it this way: a mirror is an analog computer, a cell phone with a self facing camera, with the camera turned on, is a digital computer.