Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Biology of the Physarum polycephalum Plasmodium: Preliminaries for Unconventional Computing Read chapter Read first chapter

2016 | OriginalPaper | Chapter

Towards a Non-quantum Implementation of Shor’s Factorization Algorithm

Author : Ed Blakey

Published in: Advances in Physarum Machines

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

It has been established that Physarum polycephalum slime-mould organisms retain the time-period of a regular pulse of brief stimuli. We ask whether a period can equally well be imparted not via regular pulses, but via more general periodic functions—for example via stimulus intensity varying sinusoidally with time, or even varying with time as a function with unknown period (whence the organisms not merely retain the period, but in a sense compute it); we discuss this theoretically, and also outline, though defer to future work, an experimental investigation. As motivation, we note that the ability to determine a function’s period is computationally highly desirable, not least since from such ability follow methods of integer factorization. Specifically, the phenomena described herein afford a novel (albeit inefficient), non-quantum implementation of Shor’s algorithm; inefficiency aside, this offers interesting, alternative perspectives on approaches to factorization and on the computational uses of Physarum.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Multi-agent Slime Mould Computing: Mechanisms, Applications and Advances
next chapter Modelling Oscillatory Behaviour of Slime Mould
Footnotes
1
More generally, we consider in the present work the possibility of using the moulds amongst other substrates—see Sect. 4.1—, though focus here on Physarum chiefly because of its central status in [15].
 
2
The exact form of stimulus considered in [15] is an imposition of “unfavourable [cooler, less humid] conditions”—specifically, a temperature of 23 \(^{\circ }\mathrm {C}\) and a humidity of \(60\,\%\), rather than the usual, favourable 26 \(^{\circ }\mathrm {C}\) and \(90\,\%\). In the experimental set-up of [15], a ‘pulse’ of such conditions lasts for 10 min; for context, the duration of experiments of this sort is typically of the order of hours (rather than, say, minutes or days).
 
3
The response sought and observed in [15] is a drop in the locomotive speed of the organism.
 
4
We suppose for convenience that n is odd, composite and not a prime power, which supposition is unproblematic since the condition can be checked efficiently by Turing machine, and, should it fail, a prime factor can be found, again by Turing machine, again efficiently, without ever having to invoke Shor’s algorithm.
 
5
Contrast this situation with more general periodic sequences, in which a value may be revisited several times during one period: certainly the period of the sequence 1, 2, 1, 3, 1, 2, 1, 3, ... is not 2, despite what the positions of the ‘1’s may lead one to suppose.
 
6
In an experimental context, this exposure consists of interpreting the training function as mapping time to stimulus intensity. See Sect. 3.2.1 for details.
 
7
We treat the values of a and n as being fixed and understood, and accordingly leave these values implicit by writing ‘f’ rather than ‘\(f_{a,n}\)’ or similar.
 
8
In the language of our function f above, this pulse function is given by, say, \(f' :t \mapsto {\left\{ \begin{array}{ll} 1 &{} \text {if } {\left\lfloor t\right\rfloor \equiv 0 \pmod r }\\ 0 &{} \text {otherwise} \end{array}\right. }\), which represents a unit-duration pulse every r units of time. In the experimental set-up of [15], the unit of time (and, hence, the duration of each pulse) is of the order of 10 min, and r is of the order of six (though other periods are also considered).
 
9
A topic for future study is non-linear interpolation, which may for example exaggerate differences between values of \(f^{\left( j\right) }\), thus alleviating precision-complexity [4] requirements relating to the degree of control over physical stimulus intensity—see Sect. 3.3.2.
 
10
Recall that, initially, we focus on Physarum, and defer the consideration of other substrates largely to subsequent work.
 
Literature
1.
2.
Belousov, B.: A periodic reaction and its mechanism. In: Oscillations and Traveling Waves in Chemical Systems. Wiley (1985). ISBN: 978-0-471-89384-4
3.
4.
5.
6.
7.
Brent, R.P.: Recent progress and prospects for integer factorisation algorithms. In: Du, D.-Z., Eades, P., Sharma, A.K., Lin, X., Estivill-Castro, V. (eds.) COCOON 2000, LNCS, vol. 1858, pp. 3–22. Springer, Heidelberg (2000)
8.
9.
Krieger, J., Spitzer, S.: Non-traditional, non-volatile memory based on switching and retention phenomena in polymeric thin films. In: Proceedings of Non-Volatile Memory Technology Symposium, pp. 121–124 (2004). doi:10.​1109/​NVMT.​2004.​1380823
10.
11.
Martín-López, E., Laing, A., Lawson, T., Alvarez, R., Zhou, X.-Q., O’Brien, J.: Experimental realization of Shor’s quantum factoring algorithm using qubit recycling. Nat. Photon. 6(11), 773–776 (2012). doi:10.​1038/​nphoton.​2012.​259
12.
Nakagaki, T., Yamada, H., Tóth, Á.: Intelligence: Maze-solving by an amoeboid organism. Nature 407(6803), 470 (2000). doi:10.​1038/​35035159
13.
Nielsen, M., Chuang, I.: Quantum Computation and Quantum Information. Cambridge University Press (2000). ISBN: 0-521-63503-9
14.
Rivest, R., Shamir, A., Adleman, L.: A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM 21(2), 120–126 (1978). doi:10.​1145/​359340.​359342
15.
16.
17.
18.
19.
Metadata
Title
Towards a Non-quantum Implementation of Shor’s Factorization Algorithm
Author
Ed Blakey
Copyright Year
2016
Book
Advances in Physarum Machines

Print ISBN: 978-3-319-26661-9

Electronic ISBN: 978-3-319-26662-6

Copyright Year: 2016

DOI
https://doi.org/10.1007/978-3-319-26662-6_23

Premium Partner

    Image Credits