Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Quantum Computational Speedup For The Minesweeper Problem
Uppsala University, Disciplinary Domain of Science and Technology, Physics, Department of Physics and Astronomy, Theoretical Physics.
Uppsala University, Disciplinary Domain of Science and Technology, Physics, Department of Physics and Astronomy, Theoretical Physics.
2017 (English)Independent thesis Basic level (degree of Bachelor), 10 credits / 15 HE creditsStudent thesis
Abstract [en]

Quantum computing is a young but intriguing field of science. It combines quantum mechanics with information theory and computer science to potentially solve certain formerly computationally expensive tasks more efficiently. Classical computers are based on bits that can take on the value zero or one. The values are distinguished by voltage differences in transistors. Quantum computers are instead based on quantum bits, or qubits, that are represented physically by something that exhibits quantum properties, like for example electrons. Qubits also take on the value zero or one, which could correspond to spin up and spin down of an electron. However, qubits can also be in a superposition state between the quantum states corresponding to the value zero and one. This property is what causes quantum computers to be able to outperform classical computers at certain tasks. One of these tasks is searching through an unstructured database. Whereas a classical computer in the worst case has to search through the whole database in order to find the sought element, i.e. the computation time is proportional to the size of the problem, it can be shown that a quantum computer can find the solution in a time proportional to the square root of the size of the problem. This report aims to illustrate the advantages of quantum computing by explicitly solving the classical Windows game Minesweeper, which can be reduced to a problem resembling the unstructured database search problem. It is shown that solving Minesweeper with a quantum algorithm gives a quadratic speedup compared to solving it with a classical algorithm. The report also covers introductory material to quantum mechanics, quantum gates, the particular quantum algorithm Grover's algorithm and complexity classes, which is necessary to grasp in order to understand how Minesweeper can be solved on a quantum computer.

Place, publisher, year, edition, pages
2017. , 27 p.
Series
TVE, TVE-F 17 025 juni
Keyword [en]
Minesweeper, quantum computing
National Category
Other Computer and Information Science Other Physics Topics
Identifiers
URN: urn:nbn:se:uu:diva-325945OAI: oai:DiVA.org:uu-325945DiVA: diva2:1117706
Educational program
Master Programme in Engineering Physics
Supervisors
Examiners
Available from: 2017-07-04 Created: 2017-06-29 Last updated: 2017-07-04Bibliographically approved

Open Access in DiVA

fulltext(664 kB)48 downloads
File information
File name FULLTEXT01.pdfFile size 664 kBChecksum SHA-512
cc74ca2d73a5a8db4cbaa1c8fe380992caa45eec1fe28f7df2c0b61d60238338414b914c41d2ba859f362ec716445cc33fa863430ac940d760e6b9c1e8738485
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Terner, Olof
By organisation
Theoretical Physics
Other Computer and Information ScienceOther Physics Topics

Search outside of DiVA

GoogleGoogle Scholar
Total: 48 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 213 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf