# Background

Phase estimation circuits prepare $$n$$ qubits $$Q_0, \dots, Q_{n-1}$$ in the $$|+\rangle$$ state, then apply $$U^{2^q}$$ controlled by $$Q_q$$ for each $$q$$, then apply a quantum Fourier transform, then measure $$Q_0, \dots, Q_{n-1}$$.

"Qubit recycling" refers to the fact that you can rearrange the phase estimation circuit so that $$Q_{k}$$ is measured and done with before you need to initialize $$Q_{k+1}$$, allowing a single qubit to iteratively play the roles of $$Q_0, \dots, Q_{n-1}$$. This reduces $$n$$ qubits of storage to 1 qubit of storage. Here's a diagram of phase estimation with qubit recycling:

The binary representation of an integer is a series of bits where the bit at offset $$k$$ has a "weight" of $$2^k$$. The integer is the sum of the weights of the bits that are 1. The Zeckendorf representation is similar, but the k'th bit's weight is the k'th Fibonacci number (instead of a power of 2). To make the representation unique, no two adjacent bits are set.

# Motivation

In "Space-Efficient and Noise-Robust Quantum Factoring", Ragavan and Vaikuntanathan use the Zeckendorf representation to reduce the storage of Regev's factoring algorithm. A key idea is that they replace exponentiation by repeated squaring with Fibonacci exponentiation, which allows more operations to be done inplace reducing storage. However, a consequence of this change is that they can't use qubit recycling anymore.

# Actual Question

...or can they? If I modify the phase estimation circuit so that it converts into the Zeckendorf representation before performing the controlled operations, and converts back into the binary representation before performing the QFT, is there still some way to rewrite that circuit so that it uses $$O(1)$$ storage instead of $$O(n)$$ storage? That's my question.

Here is the phase estimation circuit with a conversion into and out of Zeckendorf representation. The goal is to keep the Zeckendorf representation part (keep the fact that $$Z$$ is raised to $$t$$ times Fibonacci numbers instead of $$t$$ times powers of 2) while only having $$O(1)$$ qubits at a time.

# Attempts

I sort of made a wild guess that maybe if I just took the qubit recycling circuit and replaced $$U^{2^q}$$ with $$U^{f(q)}$$ and replaced each phase fixup $$Z^{2^a/2^b}$$ with the phase fixup $$Z^{F(a) / F(b)}$$, that that would work. So, turn this:

into this:

But you can tell from the chance display on the right hand side getting more disordered that it's not pulling out the value of $$t$$ correctly.

I also tried tweaking the input integer to be in the Zeckendorf representation, by using two qubits of workspace and using anti-controlled Hadamards to avoid having adjacent bits set. But that also didn't work:

• Although the motivation for my question is Regev's algorithm, I would consider the Gaussian distribution issue to be out-of-scope. You can assume the goal is purely to do phase estimation with O(1) space and O(n) oracle calls, but given oracles like $CU^{F(k)}$ instead of oracles like $CU^{2^k}$. Commented Feb 21 at 3:08