Home
For authors
Submission status

Current
Archive (English)
Archive
   Volumes 81-92
   Volumes 41-60
   Volumes 21-40
   Volumes 1-20
   Volumes 61-80
      Volume 80
      Volume 79
      Volume 78
      Volume 77
      Volume 76
      Volume 75
      Volume 74
      Volume 73
      Volume 72
      Volume 71
      Volume 70
      Volume 69
      Volume 68
      Volume 67
      Volume 66
      Volume 65
      Volume 64
      Volume 63
      Volume 62
      Volume 61
Search
VOLUME 71 (2000) | ISSUE 5 | PAGE 309
Relative diffusion transform and quantum speed up of computations
PACS: 03.67.Lx
It is shown that every function computable in time T(n) and space 5(n) on classical 1-dimensional cellular automaton can be computed with certainty in time 0(T1/25) and space пу/Т on a quantum computer with relative diffusion transforms (RDTs) on parts of intermediate products of the classical computation. However, RDTs in general case cannot be implemented by a conventional quantum computer even with oracles for intermediate results. Such a function can be computed only in time 0(S4sf2T/T\) on a conventional quantum computer with oracles for intermediate results of classical computations with the time Τχ.