Quantum Query Complexity to Determine Radius of a Graph

Manjula Gandhi S*, R. Prabhakar**
Periodicity:April - June'2008
DOI : https://doi.org/10.26634/jse.2.4.498

Abstract

Algorithms are the key concepts of computer science. Classical computer science provides a vast body of concepts and techniques which may be reused to great effect in quantum computing. Many of the triumphs of quantum computing have come by combining existing ideas from computer science with the ideas from quantum mechanics. The problem of determining quantum query complexity for obtaining the Radius of a graph is considered both in a classical system and in a quantum system.

Algorithms are the key concepts of computer science. Classical computer science provides a vast body of concepts and techniques which may be reused to great effect in quantum computing. Many of the triumphs of quantum computing have come by combining existing ideas from computer science with the ideas from quantum mechanics. The problem of determining quantum query complexity for obtaining the Radius of a graph is considered both in a classical system and in a quantum system.

Keywords

Quantum Computing, Qubit, Quantum Parallelism, Graph Theory, Eccentricity

How to Cite this Article?

Manjula Gandhi S and R. Prabhakar (2008). Quantum Query Complexity to Determine Radius of a Graph. i-manager’s Journal on Software Engineering, 2(4), 64-69. https://doi.org/10.26634/jse.2.4.498

References

[1]. Andrew M. Steane and Eleanor G. Rieffel (2000), ‘Beyond Bits: The future of Quantum Information Processing", IEEE potentials.
[2]. Artur Eert and Richard Jozsa (1996), ‘Quantum Computation and Shor's Factoring Algorithm‘, Review of Modern Physics, Volume 68, No.3.
[3]. Christoph Durr, Mark Heiligman, Peter Hoyer and Mchi Mhalla (2004). ‘Quantum query complexity of some graph problems‘, SIAM Journal on Computing, Vol. 35, No.b,pp.i3lO-1326.
[4]. John Clark, Derek Allan Holton [1 995) A first look at Graph Theory, Allied Publishers Ltd.
[5]. Lov K. Grover (1997), Quantum Mechanics Helps in Searching for a Needle in a Haystack, Physical Review Letters, Vol. 79, No. 2, pp.325—328.
[6]. Michael A. Nielsen, Isaac L. Chuang (2003), Quantum Computation and Quantum Information, Cambridge University Press, Cambridge.
[7]. Michel Boyer, Gilles Brassard, Peter Hoyerand Alain Tapp (T966), Tight bounds on quantum searching, Progress ofPhysics, Vol. 46, Issue 4-5, pp. 493-505.
[8]. N. David Mermin (2003), From Cbits to Qbits: Teaching Computer Scientists Quantum Mechanics, American Journal of Physics, Volume 41 , Number 23-30.
[9]. Vishal Sahni (2007), Quantum Computing, Tata McGraw—Hill, NewDelhi, India.
If you have access to this article please login to view the article or kindly login to purchase the article

Purchase Instant Access

Single Article

North Americas,UK,
Middle East,Europe
India Rest of world
USD EUR INR USD-ROW
Pdf 35 35 200 20
Online 35 35 200 15
Pdf & Online 35 35 400 25

Options for accessing this content:
  • If you would like institutional access to this content, please recommend the title to your librarian.
    Library Recommendation Form
  • If you already have i-manager's user account: Login above and proceed to purchase the article.
  • New Users: Please register, then proceed to purchase the article.