Ramanujan Graphs and Optimal Circuits
The first constructions of expander graphs (Ramanujan graphs) were given by LPS [1] using deep number theoretic methods. More recently, these constructions have found use in constructing optimal circuits (golden gates [2],[3]) and constructing LDPC codes [4].
In this talk, I will explain this construction in a self contained manner and explore its applications to the problem of gate synthesis. This is part of work in progress with Nihar Prakash Gargava, Amolak Kalra, Michele Mosca, and Jon Yard where we explore analogous constructions of expander graphs for higher dimensions and its applications to qudit circuit synthesis.
References:
[1] Hecke Operators and Distributing Points on S2 (part 2) by Lubotsky, Phillips, Sarnak
[2] 2015 - Letter to Aaronson and Pollington on the Solvay-Kitaev Theorem and Golden Gates by Sarnak
[3] Arithmeticity, thinness and efficiency of qutrit Clifford+T gates by Evra and Parzanchevski
[4] Edge Transitive Ramanujan Graphs and Highly Symmetric LDPC Good Codes by Lubotsky
Location
QNC 1201