Prime factorization using magnonic holographic devices

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-w...

Full description

Saved in:
Bibliographic Details
Published in:Journal of applied physics 2016-09, Vol.120 (12)
Main Authors: Khivintsev, Yuri, Ranjbar, Mojtaba, Gutierrez, David, Chiang, Howard, Kozhevnikov, Alexander, Filimonov, Yuri, Khitun, Alexander
Format: Article
Language:English
Subjects:
Algorithms
Applied physics
Computation
Computers
Digital computers
Factorization
Interference
Logic circuits
Mathematical analysis
MATHEMATICS AND COMPUTING
Numbers
phonons
Polynomials
Quantum computers
Quantum entanglement
Quantum mechanics
spin dynamics
spintronics
thermal conductivity
thermoelectric
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0021-8979
1089-7550
DOI:10.1063/1.4962740