Paper 2022/948

A quantum polynomial time search algorithm for certain unsorted finite lists

Abstract

Grover famously showed that any unsorted list, of finite size $N$, can be searched in O($\sqrt{N})$ time via quantum computation. Bennett et. al. demonstrated that any algorithm general enough to search any finite unsorted list must take at least O($\sqrt{N})$ time via quantum computation. We demonstrate a quantum algorithm that can search a proper subclass of finite, unsorted lists, of size $N$, in a time that is polynomial in $log(N)$. We demonstrate how it can be used to search the keyspace of any block cipher that can be implemented on a quantum computer with the keyspace in superpositon. In particular we give a polynomial time attack on $AES-128$, $AES-192$ and $AES-256$.