Jeremie Roland

We present a framework for quantum computation, similar to Adiabatic Quantum Computation (AQC), that is based on the quantum Zeno effect. By performing randomised dephasing operations at intervals determined by a Poisson process, we are able to track the eigenspace associated to a particular eigenvalue. We derive a simple differential equation for the fidelity leading to general theorems bounding the time complexity of a whole class of algorithms. We also use eigenstate filtering to optimise the scaling of the complexity in the error tolerance ε. In many cases the bounds given by our general theorems are optimal, giving a time complexity of O(1/Δ) with Δ the minimum of the gap. This allows us to prove optimal results using very general features of problems, minimising the amount of problem-specific insight necessary. As two applications of our framework we obtain optimal scaling for the Grover problem (i.e. O(N^1/2) where N is the database size) and the Quantum Linear System Problem (i.e. O(κłog(1/ε)) where κ is the condition number and ε the error tolerance) by direct applications of our theorems.

Abstract Weak coin flipping (WCF) is a fundamental cryptographic primitive for two-party secure computation, where two distrustful parties need to remotely establish a shared random bit whilst having opposite preferred outcomes. It is the strongest known primitive with arbitrarily close to perfect security quantumly while classically, its security is completely compromised (unless one makes further assumptions, such as computational hardness). A WCF protocol is said to have bias \epsilon if neither party can force their preferred outcome with probability greater than 1/2 + \epsilon. Classical WCF protocols are shown to have bias 1/2, i.e., a cheating party can always force their preferred outcome. On the other hand, there exist quantum WCF protocols with arbitrarily small bias, as Mochon showed in his seminal work in 2007 [arXiv:0711.4114]. In particular, he proved the existence of a family of WCF protocols approaching bias \epsilon(k)=1/(4k + 2) for arbitrarily large k and proposed a protocol with bias 1/6. Last year, Arora, Roland and Weis presented a protocol with bias 1/10 and to go below this bias, they designed an algorithm that numerically constructs unitary matrices corresponding to WCF protocols with arbitrarily small bias [STOC'19, p.205-216]. In this work, we present new techniques which yield a fully analytical construction of WCF protocols with bias arbitrarily close to zero, thus achieving a solution that has been missing for more than a decade. Furthermore, our new techniques lead to a simplified proof of existence of WCF protocols by circumventing the non-constructive part of Mochon's proof. As an example, we illustrate the construction of a WCF protocol with bias 1/14.

Weak coin flipping (WCF) is a fundamental cryptographic primitive, where two distrustful parties need to remotely establish a shared random bit, whilst having opposite preferred outcomes. A WCF protocol is said to have bias ε if neither party can force their preferred outcome with probability greater than 1/2+ε. Classical WCF protocols are shown to have bias 1/2, i.e., a cheating party can always force their preferred outcome. A lower bias can only be achieved by employing extra assumptions, such as computational hardness. On the other hand, there exist quantum WCF protocols with arbitrarily small bias, as Mochon showed in his seminal work in 2007 [arXiv:0711.4114]. In particular, he proved the existence of a family of WCF protocols approaching bias ε(k) = 1/(4k + 2) for arbitrarily large k and proposed a protocol with bias 1/6. Last year, Arora, Roland and Weis presented a protocol with bias 1/10 and to go below this bias, they designed an algorithm that numerically constructs unitary matrices corresponding to WCF protocols with arbitrarily small bias [STOC’19, p.205-216]. In this work, we present new techniques which yield a fully analytical construction of WCF protocols with bias arbitrarily close to zero, thus achieving a solution that has been missing for more than a decade. Furthermore, our new techniques lead to a simplified proof of existence of WCF protocols by circumventing the non-constructive part of Mochon’s proof. The construction of an explicit WCF protocol approaching bias 1/14 is illustrated as an example.