fairfolio
Saved Projects

Quantum Bogosort

ISEF · 2022 Systems Software

Huebner, George · Walter Payton College Preparatory High School

Overview

Quantum computers promise to revolutionize several scientific fields by solving and simulating certain problems significantly faster than their classical counterparts. However, very few people currently have the skillset to take advantage of this extra computing power. We implemented a joke algorithm on a quantum computer in order to teach fundamental quantum computing concepts to a broader audience and to spread awareness about this exciting new technology. Bogosort is a (bad) sorting algorithm that tries to sort a list by randomly permuting it. Quantum bogosort is conceptually similar to classical bogosort, except it leverages a property of quantum computers known as “superposition” in order to generate all possible permutations of a list at once. We created a recursive algorithm that superimposes a range of integers, which effectively acts as a quantum random number generator to determine how the list is permuted. Most performance metrics (e.g. gate count and error rate) scale with the number of ones in the binary representation of the number of permutations of the list. This effectively means that while numbers slightly greater than or equal to powers of two perform extremely well, numbers slightly less than powers of two perform extremely poorly. Quantum bogosort had an average runtime of 200 seconds on a 7 element list. Although the sorting capabilities of quantum bogosort are not useful, it provides a quirky, applied example of practical problem solving with quantum computers. Additionally, the algorithm used for arbitrary superposition provided interesting insight into preparing entanglement using recursive methods.

Competition history

Resources

Related projects

Closest projects by meaning, across every fair and year in the corpus.

Browse more like this

Source: Regeneron International Science and Engineering Fair

Save projects to your library

Sign in with Google to keep track of projects you find interesting, organized into folders. An account also raises your daily allowance for “Has this been done?”, and lets you create a key for the MCP server with a much higher limit than anonymous use. Browsing stays public.

Continue with Google