Prime factorization using magnonic holographic devices
Abstract
Determining the prime factors of a given number N is a problem that requires super-polynomial time for conventional digital computers. A polynomial-time algorithm was invented by Shor for quantum computers. In this paper, we present experimental data that demonstrate prime factorization using spin-wave interference but without quantum entanglement. Prime factorization includes three major steps. First, a general-type computer calculates the sequence of numbers mkmod(N), where N is the number to be factorized, m is a randomly chosen positive integer, and k = 1, 2, 3, 4, 5, 6…. Next, the period of the calculated sequence r is determined by exploiting spin-wave interference. Finally, the general-type computer determines the primes based on the obtained r. The experiment for period finding was conducted on a six-terminal Y3Fe2(FeO4)3 device. We chose number 15 for testing and determined its primes using a sequence of measurements. The obtained experimental data for a micrometer-sized prototype aimed to demonstrate the benefits of using spin-wave devices to solve complex computational problems. Scalability is one of the major strengths inherent in this type of wave-based device, which may provide a route to nanometer-sized logic circuits. We discuss the physical and technological limitations of this approach, which define the maximum size of N and the computational speed. Although this classical approach cannot compete with the quantum algorithm in terms of efficiency, magnonic holographic devices can potentially be used as complementary logic units aimed at speeding up prime factorization for classical computers.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Sep 22, 2016
- Source ID
- 10.1063/1.4962740
Entities
People
- Alexander Khitun
- Alexander Kozhevnikov
- David Gutierrez
- Howard Chiang
- Mojtaba Ranjbar
- Yuri Filimonov
- Yuri Khivintsev
Organizations
- Defense Advanced Research Projects Agency
- University of California
- V.A. Kotelnikov Institute of Radio-engineering and Electronics