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, (2^{K}-(#PrimesLessThan(2^{K})))! 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 2^{K}-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(x^{1/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*).