Reversible Logic Synthesis Benchmarks Page

you are in... Main\n-th prime

Function nth_primeK has K inputs and K outputs. For an input value n this function returns n-th prime, as long as this prime may be written (in binary) using at most K bits. Enumeration of primes starts with one, in that zeroth prime, nth_primeK(0), may be anything that is not equal to a prime, e.g., zero. For sufficiently large K, nth_primeK(1)=2, nth_primeK(2)=3, nth_primeK(3)=5, nth_primeK(4)=7, nth_primeK(5)=11, etc.

As described, nth_primeK, is an incomplete specification, as some inputs do not have a valid output. There are many ways, (2K-(#PrimesLessThan(2K)))! in particular, to extend nth_primeK to a reversible specification, even without adding any new input bits. One of them is to fill the unassigned outputs with an increasing sequence of zero, one and composite numbers between 4 and 2K-1. This results in the reversible specification nth_primeK_inc.

Why is this function and any of its reversible extensions interesting? Classically, the best known algorithm to compute nth_primeI has an exponential complexity (about sqrt(2)K due to reducibility, via binary search, to the problem of computing the number of primes p<=x, whose best known solution requires O(x1/2+e) time for any e>0) in the number of input bits, K. Thus, any reversible circuit for any reversible specification completing nth_primeK is expected to contain an exponential number of gates. Should a polynomial size reversible circuit using a polynomial number of ancilla bits be found, it will be a major breakthrough.

Currently, nth_primeK and any of its reversible extensions form a family of most difficult functions in terms of their practical (as opposed to theoretical) circuit complexity. Indeed, all other functions currently available on this web page (excluding permanent) allow a polynomial size circuit if a small (at most linear, if at all) number of auxiliary bits is available (see here for the discussion of efficient circuits for hwb).