Inventions, Physics

Researchers make breakthrough in quantum computation: factoring a number in prime numbers

If you did intermediate math in school, then you’ll most likely remember how to split numbers into prime factors; basically, any number can be written out by multiplying prime factors. Now, a group of researchers from UC Santa Barbara has designed and fabricated a quantum processor capable of factoring a composite number. Don’t get overexcited though, because the number is quite small: 15.

Why it matters

Although extremely modest compared to common such calculations done for numbers with many digits, the achievement represents a significant milestone in quantum computerdevelopment, which will ultimately bring significant improvements to cryptography and cybersecurity.

“Fifteen is a small number, but what’s important is we’ve shown that we can run a version of Peter Shor’s prime factoring algorithm on a solid state quantum processor. This is really exciting and has never been done before,” said Erik Lucero, the paper’s lead author.

Scaling it up

“What is important is that the concepts used in factoring this small number remain the same when factoring much larger numbers,” said Andrew Cleland, a professor of physics at UCSB and a collaborator on the experiment. “We just need to scale up the size of this processor to something much larger. This won’t be easy, but the path forward is clear.”

Much like many other quantum computers, this achievement was motivated by practical applications; the backbone of cybersecurity is represented by very large numbers, and quantum computers, although in their infancy, can go much beyond today’s computer capabilities.

“Anytime you send a secure transmission — like your credit card information — you are relying on security that is based on the fact that it’s really hard to find the prime factors of large numbers,” he said.

Quantum computers and qubits

Unlike today’s computers, which work with 0 and 1, quantum computers rely on quantum processes such as supersposition and entanglement, and instead of bits, uses quantum bits, or qubits. Whereas digital computers require data to be encoded into binary digits (bits), quantum computation utilizes quantum properties to represent data and perform operations on these data – and the computation power grows enormously. For example, factoring out a number with 600 digits would take a supercomputer longer than the age of the universe, while with a quantum computer, it could take only a couple of hours.

“A quantum computer can solve this problem faster than a classical computer by about 15 orders of magnitude,” said Lucero. “This has widespread effect. A quantum computer will be a game changer in a lot of ways, and certainly with respect to computer security.”

The next step, according to Lucero, is to increase the quantum coherence times and go from nine quantum elements to hundreds, then thousands, and on to millions. “Now that we know 15=3×5, we can start thinking about how to factor larger — dare I say — more practical numbers,” he said.

Via UCSB

  • chriwi

    If this is already published via facebook I really wonder if CIA or Mossad not already have quantumcomputers that make all cryptography used today obsolet.

  • deatos

    It dont make “all” cryptography obsolete, for instance xor crypto with one time keys is not suseptable to quantum cracking.

  • Nick Fisher

    Umm well… while strictly speaking a one-time is thoretically uncrackable, in practice the cryptanalist will always have some contextual information, and pulling on that thread often unravels all sorts of interesting patterns… ;)