In my previous post, I mentioned that a forthcoming paper would explore Fibonacci exponentiation in more detail.
I’ve just completed the paper, posted here.
The paper explores targeted exponentiation algorithms, which compute a group exponentiation operation b = ak with a reversible circuit in such a way that the initial state of the algorithm consists only of the base a and fixed values, and the final state consists of only the exponential b and other fixed values.
In conventional applications of exponentiation, it’s sufficient just that the final state include the exponential b; the other values don’t matter. Moreover, in conventional applications, the circuit doesn’t need to be reversible.
In quantum computing applications, in contrast, the circuit is reversible by definition. The “targeting” helps because it ensures that the individual exponentials in the output are “unentangled” with other side values.
As it turns out, Fibonacci exponentiation algorithms are well suited for reversible computing and for targeted exponentiation, and are more efficient than their conventional, binary counterparts for these purposes. The paper compares three approaches.
The paper started as a search for an efficient algorithm for “generic” exponentiation in one variant of the quantum magic box. That led to a review of the literature involving Fibonacci numbers. One of the recent results was a paper by a faculty member I worked for in my first teaching position, nearly three decades ago. His algorithm was directed to a very different problem involving properties of the extended Fibonacci Zeckendorf array — but our solutions turned out to be quite complementary.
I’m encouraged to see the applications that continue to emerge in so many fields of mathematics — and grateful to be able to reconnect with people contributing to them as I write these occasional papers.
— Burt
Update: The paper is now posted as arXiv:1711.02491 [math.NT].
Quantum Magic Box 