143 is largest number yet to be factored by a quantum algorithm

Apr 11, 2012 by Lisa Zyga feature
Quantum factorization of 143 using the adiabatic quantum algorithm. As the system evolves to its ground state k = 6, it reaches a superposition of states 6 and 9, which denotes the answers 11 and 13. Image credit: Xu, et al. ©2012 American Physical Society

(Phys.org) -- While factoring an integer is a simple problem when the integer is small, the complexity of factorization greatly increases as the integer increases. When the integer grows to more than 100,000 or so digits, the problem reaches a point at which it becomes too complex to solve using classical computing methods. But quantum computers, with their use of entanglement and superposition, can theoretically factor a number of any size. However, the largest number that has been factored on a quantum processor so far is 21. Now in a new study, physicists have set a new record for quantum factorization by developing the first quantum algorithm that can factor a three-digit integer, 143, into its prime factors, 11 and 13.

The , Nanyang Xu at the University of Science and Technology of China in Hefei, China, have published their study on the new quantum computation algorithm in a recent issue of . They explain that, despite the potential for factoring any size number, quantum algorithms still face fundamental challenges.

“Quantum algorithms can theoretically solve the factoring problem; however, it is still challenging for today’s technologies to control a lot of qubits for a long enough time to factor a larger number,” Xu told Phys.org. “The environmental noises and other imperfections make the quantum system so fragile that decoherence could destroy everything stored in qubits in a short time.”

As the physicists note in their study, the first and most well-known for factorization is Shor's algorithm, which was developed by mathematician Peter Shor in 1994. This algorithm, which involves quantum , is based on a circuit model in which a sequence of operations is performed to solve the problem.

In the current study, Xu and coauthors use an alternative to Shor's algorithm called adiabatic quantum computation (AQC). Proposed by Edward Farhi, et al., in 2001, AQC was developed for optimization problems, in which the best value of many possible values is sought. Several computational problems, including factoring, have been formulated as optimization problems and then solved using AQC. Here, the scientists' algorithm builds on one of these formulations by Peng, et al., in 2008, which used AQC to factor the largest number before now, 21.

Unlike Shor's algorithm, AQC does not run through a sequence of operations, but instead relies on quantum adiabatic processes. More specifically, the algorithm finds a mathematical function called the Hamiltonian in which all possible solutions are encoded as eigenstates, and the correct solution is encoded as the ground state. To solve a problem, the algorithm gradually evolves the Hamiltonian according to a mathematical equation, resulting in the system reaching its ground state and providing the correct answer. (In its physical implementation, the system consists of a liquid-crystal nuclear magnetic resonance (NMR) system like those used in magnetic resonance imaging (MRI), in which magnetic nuclei absorb and re-emit radiation at a specific frequency.)

While the adiabatic-based strategy works well in theory, in reality it still faces challenges when factoring large numbers because the Hamiltonian's spectrum of all possible eigenstates grows exponentially with the size of the integer. So Xu and coauthors developed a way to suppress the spectrum's growth by simplifying the mathematical equations governing the Hamiltonian. In the end, the physicists' simplified equations significantly decreased the growth rate of the spectrum to make it easier to factor larger numbers than before.

“We use a new method and reduce the qubits needed in the algorithm, which finally made the factorization of 143 available in realization,” Xu said. “Our work shows the practical importance of the adiabatic quantum algorithm.”

In the future, the strategies used here could lead to even larger integer factorization by quantum algorithms.

“It is possible to factor a larger number using the strategies in our current paper on current platforms,” Xu said. “In this issue, we plan to improve our control ability towards the NMR quantum processor to factor a larger number, and the exact time complexity of the algorithm is still an open question.”

Explore further: Tiny magnetic sensor deemed attractive

More information: Nanyang Xu, et al. “Quantum Factorization of 143 on a Dipolar-Coupling Nuclear Magnetic Resonance System.” PRL 108, 130501 (2012). DOI: 10.1103/PhysRevLett.108.130501

4.5 /5 (22 votes)

Related Stories

Madrid duo fire up quantum contender to Google search

Dec 14, 2011

(PhysOrg.com) -- Two Madrid scientists from The Complutense University think they have an algorithm that may impact the nature of the world's leading search engine. In essence, they are saying Hey, world, ...

Solving big problems with new quantum algorithm

Nov 09, 2009

(PhysOrg.com) -- In a recently published paper, Aram Harrow at the University of Bristol and colleagues from MIT in the United States have discovered a quantum algorithm that solves large problems much faster ...

Recommended for you

Tiny magnetic sensor deemed attractive

9 hours ago

Ultra-sensitive magnetic sensor technology pioneered at PML may soon be commercialized for a host of applications from detection of unexploded bombs and underground pipes to geophysical surveying and perhaps ...

Beams come knocking on the LHC's door

10 hours ago

Over the weekend, proton beams came knocking on the Large Hadron Collider's (LHC) door. Shooting from the Super Proton Synchrotron (SPS) and into the two LHC injection lines, the proton beams were stopped ...

Climate control in termite mounds

12 hours ago

When they make their way into homes, some species of termites can be destructive pests. Their fungus-harvesting relatives in Africa and Asia, however, are known for their construction prowess, collectively ...

The secret of dragonflies' flight

12 hours ago

Dragonflies can easily right themselves and maneuver tight turns while flying. Each of their four wings is controlled by separate muscles, giving them exquisite control over their flight.

User comments : 10

Adjust slider to filter visible comments by rank

Display comments: newest first

Tennex
1 / 5 (2) Apr 11, 2012
If the computational power of classical computers is limited with uncertainty principle, why the computational power of quantum computers should be higher?
Vendicar_Decarian
0.3 / 5 (37) Apr 11, 2012
Ahahahahaha... At first I thought that 143 was the number of digits.
marciot
5 / 5 (2) Apr 11, 2012
Ah, shucks! They cracked my private/public key pair :(
Lurker2358
1 / 5 (5) Apr 12, 2012
Great. 11 and 13, the largest two primes that each fit in a half-byte.

We are just blazing ahead with this quantum technology.

How many million dollars did this cost to develop this computer?
Aliensarethere
not rated yet Apr 12, 2012
Did they even use a quantum computer for this ? It's not clear from the article.
Tigah
not rated yet Apr 12, 2012
Did they even use a quantum computer for this ? It's not clear from the article.


I'm going with a yes BUT, based on: "Quantum algorithms can theoretically solve the factoring problem; however, it is still challenging for todays technologies to control a lot of qubits for a long enough time to factor a larger number, Xu told Phys.org. The environmental noises and other imperfections make the quantum system so fragile that decoherence could destroy everything stored in qubits in a short time.

As the physicists note in their study, the first and most well-known quantum algorithm for factorization is Shor's algorithm, which was developed by mathematician Peter Shor in 1994. This algorithm, which involves quantum entanglement, is based on a circuit model in which a sequence of operations is performed to solve the problem."

So, it's a shady yes.
antialias_physorg
3.9 / 5 (7) Apr 12, 2012
How many million dollars did this cost to develop this computer

According to you we should have never started banging rocks together because the development of fire was still some days in the future.

Think of in what kind of abject poverty and terrible medical conditions you would be living in right now if we hadn't spent the occasional dollar on fundamental science in the past.

If you're over thirty you'd be likely already dead without it. So stop your whining.
slayerwulfe
not rated yet Apr 12, 2012
the human condition: a corporeal linear existence witnessing a new birth and hoping that intelligence as an attribute will finally exceed socially, entertainers and athlete's. i'm going back to my studies rather than discuss my perceived insights of quantum math in it's various forms. aarrrggghhh i'm so driven envious and jealous.
Lurker2358
2 / 5 (4) Apr 12, 2012
According to you we should have never started banging rocks together because the development of fire was still some days in the future.


Not quite.

We already have classical computers that can factor numbers larger than ordinary human comprehension, so it's quite a different animal.

At the rate things are progressing, they are still about 20 to 30 years or more away from creating a quantum computer that actually out-performs a mid-1990's era PC, even in simple "quantum-friendly" situations.

and it will probably cost a billion dollars each to do that.

It looks like quantum computers be factoring the first mega-byte sized number in about 30 years.

Normal computers did that several decades ago.
wwqq
not rated yet Apr 18, 2012
We already have classical computers that can factor numbers larger than ordinary human comprehension, so it's quite a different animal.


No, we do not have that. With conventional computers 128-bit symmetric keys are considered effectively unbreakable.

It looks like quantum computers be factoring the first mega-byte sized number in about 30 years.


No, it will make non-special 128 bit numbers factorizable, but 256 bit numbers will still be out of reach.

Normal computers did that several decades ago.


Laughably wrong.

Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.