Quantum Magic Box

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 = a^k 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].

I’ve just posted an updated version of the paper.  Most of the changes are editorial, but there are also two substantive improvements:

(1) Sec. 6.3 now proposes Fibonacci exponentiation as a potential way to implement a generic exponentiator that could produce the “elusive” eigenstate.  (Fibonacci exponentiation methods will be explored further in a forthcoming paper.)

(2) A new Sec. 6.8 describes an approach where multiple magic box implementations collaborate to solve a discrete logarithm problem

— Burt

• Update:  The paper is now posted as IACR ePrint 2017/745.

For public-key cryptosystems based on integer factoring and the discrete logarithm problem, the focus of quantum algorithms research to date, inspired by Peter Shor’s elegant discovery, has been on optimizing algorithms that can break an instance of the cryptosystem, i.e., solve for a private key given a public key, with a single run of the quantum computer.

That may be asking too much of a quantum computer, given the primitive state of implementation.

It may be better to ask instead, what is the minimum that a quantum computer needs to do in a single run, in order for an overall algorithm — including the portion run on a classical computer — to break a cryptosystem?

For the discrete logarithm problem, that question has a well-established answer from research over 30 years ago by Manuel Blum and Silvio Micali.

In their foundational paper on pseudorandom generation, Blum and Micali showed that the discrete logarithm problem could be solved efficiently given a “magic box” that computes the most significant bit of the discrete logarithm with a slight advantage over guessing.

That’s a potentially much easier problem to solve on a quantum computer (though still complex).  Rather than solving for a full discrete logarithm nearly perfectly in a single run, the quantum computer would only need to solve for a single bit of the discrete logarithm, and only approximately on average.

As shown in the attached paper, it appears to be possible to realize this magic box with an improvement of Michele Mosca and Artur Ekert’s variant of Shor’s algorithm.

It’s not clear at this point how much benefit, if any, this new quantum magic box will have in practice.  However, the new algorithm offers another approach for the ongoing optimization of quantum algorithms for breaking the discrete logarithm problem over both finite fields and elliptic curves.  The reader is encouraged to analyze, improve — and find flaws.

— Burt Kaliski