Is QFT qubit recycling compatible with Zeckendorf's Fibonacci representation of integers?

Question

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:

source: https://arxiv.org/abs/1706.07884

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:

Answer 1

My spontaneous off-the-bat reply would be no — and even if control qubits can be recycled, then it would be towards the end of the quantum algorithm, and the advantage would then not be that great. This assuming that one does not also change the way in which the arithmetic is performed (and the way in which the control registers are initialized, and hence the analysis).

Basically — when using the Fibonacci-based exponentiation of Ragavan and Vaikuntanathan to implement Regev's quantum factoring algorithm — the control registers are first initialized to a discretized Gaussian distribution (not a uniform distribution) and then mapped to Zeckendorf representation. The product is then computed (using the control registers) and copied out to a separate register. The product is then uncomputed (again using the control registers), and the control registers mapped back to standard representation. It is only at this point that the QFTs are applied, and readouts occur.

Given the above, I would think that if one can recycle control qubits, it would be towards the end of the algorithm, during or after the uncomputation of the product. Furthermore, I note that we typically need a uniform initialization of the control register to apply the semi-classical QFT with control qubit recycling. One can maybe think of the low-order control qubits as uniform when using a discretized Gaussian initialization, but the whole control register will not be uniform in this case.

For similar reasons, I note that it is not straightforward to apply qubit recycling to Regev's original algorithm either: The product has to be uncomputed (using the control registers), and the control registers are initialized to a discretized Gaussian distribution.