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

Discussion in 'Science and Technology' started by Matthew, Apr 11, 2012.

  1. Matthew
    Offline

    Matthew Blue dog all the way!

    Joined:
    Mar 16, 2010
    Messages:
    49,694
    Thanks Received:
    4,596
    Trophy Points:
    1,885
    Location:
    Portland Oregon
    Ratings:
    +15,167
    143 is largest number yet to be factored by a quantum algorithm
    April 11, 2012 by Lisa Zyga
    Enlarge
    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 physicists, 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 Physical Review Letters. 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 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.

    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 quantum computing 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.”
    143 is largest number yet to be factored by a quantum algorithm
     
  2. Matthew
    Offline

    Matthew Blue dog all the way!

    Joined:
    Mar 16, 2010
    Messages:
    49,694
    Thanks Received:
    4,596
    Trophy Points:
    1,885
    Location:
    Portland Oregon
    Ratings:
    +15,167
    Quantum internet: Physicists build first elementary quantum network
    April 11, 2012
    Enlarge
    Single atoms form the nodes of an elementary quantum network in which quantum information is transmitted via the controlled exchange of single photons. Graphic by Andreas Neuzner, MPQ

    (Phys.org) -- A team of scientists at the Max Planck Institute of Quantum Optics realizes a first elementary quantum network based on interfaces between single atoms and photons.


    Whether it comes to phoning a friend or to using the internet – our daily communication is based on sophisticated networks, with data being transferred at the speed of light between different nodes. It is a tremendous challenge to build corresponding networks for the exchange of quantum information. These quantum networks would differ profoundly from their classical counterparts: Besides giving insights into fundamental questions in physics, they could also have applications in secure communication and the simulation of complex many-body systems, or they could be used for distributed quantum computing. One prerequisite for functional quantum networks are stationary nodes that allow for the reversible exchange of quantum information.

    A major breakthrough in this field has now been achieved by scientists in the group of Professor Gerhard Rempe, director at the Max Planck Institute of Quantum Optics and head of the Quantum Dynamics division: The physicists have set up the first elementary quantum network. It consists of two coupled single-atom nodes that communicate quantum information via the coherent exchange of single photons. “This approach to quantum networking is particularly promising because it provides a clear perspective for scalability”, Professor Rempe points out.

    Quantum information is extremely fragile and cannot be cloned. In order to prevent alteration or even the loss of the information, it is necessary to have perfect control over all quantum network components. The smallest stationary memory for quantum information is a single atom, and single photons represent the perfect messengers. Efficient information transfer between an atom and a photon, however, requires strong interaction between the two, which cannot be achieved with atoms in free space. Following a proposal from Professor Ignacio Cirac (director at the MPQ and head of the Theory division), the group of Professor Rempe has invested many years working on systems in which single atoms are embedded in optical cavities. These cavities are composed of two highly reflecting mirrors placed at a very short distance. The emission of photons from an atom inside a cavity is directed and can therefore be sent to other network nodes in a controlled way. A photon entering the cavity is reflected between the mirrors several thousand times. In this way, the atom-photon interaction is strongly enhanced, and the atom can absorb the photon coherently and with high efficiency.




    The first experimental challenge was to quasi-permanently trap the atom in the cavity. This was achieved via fine-tuned laser beams, meaning the least disturbance of the atom. In the next step, the physicists achieved controlled emission of single photons from the trapped atom. Finally, they could prove that the single-atom-cavity system represents a perfect interface for storing the information encoded in a single photon, and they were able to transfer it onto a second single photon after a certain storage time. The present work is another milestone on the way towards a large-scale quantum network. For the first time, two such systems were connected, and quantum information was exchanged between them with high efficiency and fidelity. The two systems, each representing a network node, are installed in two laboratories separated by 21 metres and are connected via a 60-metre long optical fibre.

    Quantum networks exhibit peculiar properties not found in their classical counterparts. This is due to the fundamentally different behaviour of the exchanged information: while a classical bit represents either 1 or 0, a quantum bit can take both values at the same time, a phenomenon called “coherent superposition”. A measurement however projects the quantum bit onto one of the two values. In the single atom, the quantum information is encoded in a coherent superposition of two energy levels. When the atom at node A emits a photon, stimulated by a light pulses from a control laser, its quantum state is mapped onto the polarization state of the photon. Via the optical fibre the photon reaches node B where it is coherently absorbed. During this process, the quantum state originally prepared in atom A gets transferred onto the atom at node B. As a result, A is capable of receiving the next photon, while B is ready to send the stored information back to A or to any other node. It is this symmetric and reversible feature that makes the scheme scalable to arbitrary network configurations, consisting of many atom-cavity nodes. The atomic quantum states are read out by mapping them again onto the polarization of single photons which can easily be measured. “We were able to prove that the quantum states can be transferred much better than possible with any classical network. In fact, we demonstrate the feasibility of the theoretical approach developed by Professor Cirac,” Dr. Stephan Ritter, leader of the experiment, explains.

    In yet another step the scientists succeeded in generating “quantum mechanical entanglement” between the two nodes. Entanglement is a feature unique to quantum objects. It connects them in such a way that their properties are strongly correlated in a non-trivial way, no matter how far they are separated in space. This phenomenon, predicted nearly a hundred years ago, was dubbed by Albert Einstein (who did not really believe in it) “spooky action at a distance”. In order to achieve entanglement between the two network nodes, the polarization of the single photon emitted by atom A is now entangled with the atomic quantum state. Once the photon gets absorbed, this entanglement gets transferred onto atom B. In fact, this is the first time that entanglement has been created between massive particles separated by such a large distance, making it the world’s “largest” quantum system with massive particles.

    “We have realized the first prototype of a quantum network”, Stephan Ritter concludes. “We achieve reversible exchange of quantum information between the nodes. Furthermore, we can generate remote entanglement between the two nodes and keep it for about 100 microseconds, whereas the generation of the entanglement takes only about one microsecond. Entanglement of two systems separated by a large distance is a fascinating phenomenon in itself. However, it could also serve as a resource for the teleportation of quantum information. One day, this might not only make it possible to communicate quantum information over very large distances, but might enable an entire quantum internet.”
    Quantum internet: Physicists build first elementary quantum network
     
  3. percysunshine
    Online

    percysunshine Gold Member

    Joined:
    Feb 5, 2011
    Messages:
    16,692
    Thanks Received:
    2,261
    Trophy Points:
    280
    Location:
    Sty
    Ratings:
    +5,861
    Quantum factorization of 143 using the adiabatic quantum algorithm....

    I can factor 143 in my sleep.

    Computers have a long way to go to match the human brain.

    Which is understandable, since the human brain invented them in the first place.
     
  4. Matthew
    Offline

    Matthew Blue dog all the way!

    Joined:
    Mar 16, 2010
    Messages:
    49,694
    Thanks Received:
    4,596
    Trophy Points:
    1,885
    Location:
    Portland Oregon
    Ratings:
    +15,167
    This is still a cool development. Worth fighting to save civlization for!
     
  5. Conservative
    Offline

    Conservative Type 40

    Joined:
    Jul 1, 2011
    Messages:
    17,082
    Thanks Received:
    2,026
    Trophy Points:
    48
    Location:
    Pennsylvania
    Ratings:
    +2,030
    [​IMG]
     
  6. Liability
    Offline

    Liability Locked Account. Supporting Member

    Joined:
    Jun 28, 2009
    Messages:
    35,447
    Thanks Received:
    5,049
    Trophy Points:
    48
    Location:
    Mansion in Ravi's Head
    Ratings:
    +5,063
    It is quite possible -- maybe even probable -- that computerized "intelligence" will outstrip its creator's "intelligence" in the relatively near future.

    See, Ray Kuzweil, The Singularity is Near. A very cool book.
     
  7. percysunshine
    Online

    percysunshine Gold Member

    Joined:
    Feb 5, 2011
    Messages:
    16,692
    Thanks Received:
    2,261
    Trophy Points:
    280
    Location:
    Sty
    Ratings:
    +5,861
    Well, some people have less intelligence than computers...so I see your point....sort of

    Outstripping a creator is a bit of a stretch.
     
    Last edited: Apr 11, 2012
  8. Liability
    Offline

    Liability Locked Account. Supporting Member

    Joined:
    Jun 28, 2009
    Messages:
    35,447
    Thanks Received:
    5,049
    Trophy Points:
    48
    Location:
    Mansion in Ravi's Head
    Ratings:
    +5,063
    :lmao:
     

Share This Page