Quantum Versions of Classical Randomized Algorithms
スポンサーリンク
概要
- 論文の詳細を見る
We present a quantum version of the classical probabilistic algorithms a'la Rabin for the test of primality of a given integer. Our quantum algorithm is based on the use of Grover's unitary operator for searching an unstructured database and of Shor's Fourier transform for extracting the periodicity of a function, and their combined use in the quantum counting algorithm by Brassard et al. Our quantum probabilistic algorithm is fully unitary and reversible, and can be used as part of larger and more complicated quantum networks. Polynomial time algorithms for testing the primality of an integer, the 'prime number theorem' and a conjecture about the asymptotic number of representations of an even integer as a sum of two primes are also discussed.
- 理論物理学刊行会の論文
- 2000-04-28
著者
-
Carlini Alberto
Physics Department Tokyo Institute Of Technology Tokyo 152 Japan
-
Hosoya A
Tokyo Inst. Technol. Tokyo Jpn
-
HOSOYA Akio
Physics Department, Tokyo Institute of Technology, Tokyo 152, Japan
-
Hosoya Akio
Physics Department Tokyo Institute Of Technology Tokyo 152 Japan
-
HOSOYA Akio
Research Institute for Theoretical Physics, Hiroshima University
-
HOSOYA Akio
Department of Physics, Osasa University
-
CARLINI Alberto
Physics Department, Tokyo Institute of Technology, Tokyo 152, Japan
関連論文
- Stochastic Quantization and the Grivob Problem in Non-Abelian Gauge Theories
- Topology Change by Quantum Tunneling in (2+1)-Dimensional Einstein Gravity : Invited Papers
- Dynamics of False-Vacuum Bubbles in (2+1)-Dimensional Gravity : Astrophysics and Relativity
- (2+1)-Dimensional Classical Gravity with Point Sources in Maximal Slice : Particles and Fields
- On Perturbation Expansion of Field Theory in Accelerated System and the Thermofield Dynamics : Particles and Fields
- A Comment on Quantum Fluctuations around Solitons
- Quantum Versions of Classical Randomized Algorithms
- Black Hole Radiation inside Apparent Horizon in Quantum Gravity : Astrophysics and Relativity
- (2+1)-Dimensional Quantum Gravity : Case of Torus Universe : Particles and Fields
- Particle Creations by Expanding Universe and Suppression of Supercooling
- Quantum Non-Abelian Gauge Theory in Time-Dependent External Fields
- Quantum Non-Abelian Gauge Theory in Time-Dependent External Fields. II
- Path-Integral for a Colour Spin and Path-Ordered Phase Factor
- Non-Abelian Magnetic Charges
- Dual Potential and Magnetic Loop Operator
- A Baryon Number Generation Mechanism in the Expanding Universe
- Quantization for Regge Slopes and ψ-Particles
- Is Anisotropic Kaluza-Klein Model of Universe Chaotic ? : Particles and Fields
- Density Fluctuation in Extended Inflationary Universe : Astrophysics and Relativity
- A Diagrammatic Derivation of Coleman's Vanishing Cosmological Constant : Particles and Fields
- Moving Mirror Effects in hadronic Reactions
- Regge-Slope Quantization and Deep-Region Behavior in Dual Resonance Models
- Effective Quark Mass in an Expanding Bag
- On Vanishing of Energy-Momentum Tensor for a Class of Instanton-Like Solutions