Quantum Bogosort

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

• ISEF 2022 Systems Software · Entry SOFT055 · Atlanta, Georgia, United States

Resources

• ISEF abstract page ↗

Related projects

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