2
$\begingroup$

Classically, it's very easy to create an incrementing function that can perform up to $n$ increments with $O(n)$ work:

class Counter:
    def __init__(self):
        self.bits = []
    def increment(self):
        for i in range(len(self.bits)):
            self.bits[i] = !self.bits[i]
            if self.bits[i]:
                return  # SHORT CIRCUIT
        self.bits.append(True)

Although any given increment may take $O(n)$ work individually, it must also create a situation where the following increments are cheap due to short-circuiting.

When working with qubits, the above approach doesn't work. The short-circuiting test would require a measurement, and various parts of the superposition would have to short-circuit at different times.

With that in mind, consider the following circuit. It keeps applying some unspecified and possibly varying operation to a qubit then doing a conditional increment:

Incrementing circuit

Each increment here is being done naively, so each of the $n$ increments requires $O(\lg n)$ gates and the overall circuit has $O(n \lg n)$ cost. Even though, within each component of the superposition, most of that work is wasted on most increments. Classically we would only need $O(n)$ gates total.

Is there some way to optimize the circuit down to $O(n)$ gates, without depending on the details of $U$?


My initial idea for this problem was to store all the controlled outcomes separately, then merge them pairwise until they were all in a single counter. That would be $O(n)$ aggregate work as desired. But for it to work identically to the original circuit you need to uncompute all the sub-counters used during merging, and the uncomputing doesn't seem to work when the counted values don't commute (e.g. if $U = H$).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.