Could an *implicitly* defined graph be a member of a *strongly-explicit* family of expanders?

Question

There seems to be a slight difference in terminology among a couple of different traditions within theoretical computer science.

• To have a quantum computer simulate the Hamiltonian evolution of $\exp(-iAt)$ of some $2^n\times 2^n$ hermitian matrix $A$ giving the adjacency matrix of a sparse undirected graph on $2^n$ vertices, it suffices that we are also provided oracle access to query different vertices to have adjacent vertices returned in order, so that we can partition the adjacency matrix $A$ with edge-colors and subsequently Trotterize the partition;
• In the theory of expanders, as explained by O'Donnell here it's a rather trivial result that most (Erdős–Rényi) sparse random graphs have good expansion properties; what applications generally require is an explicit family of graphs. But, when we are also provided oracular access to adjacent vertices, this has been referred to as a strongly explicit family of expanders; while
• Wikipedia defines an implicit graph representation as is a graph whose vertices or edges are not represented as explicit objects in a computer's memory, but rather are determined algorithmically.

It's these last two terms that I'm wondering about - is it correct to say that an implicitly defined graph could be a member of a strongly explicit family of expanders (and, if so, could it be amenable to Hamiltonian simulation)?

Answer 1

Yes! But I can see why it is confusing.

A strongly explicit graph family $\{G_n = (V_n,E_n)\}$ (parameterized e.g. by number of vertices $n$) is described by an efficient ($\mathrm{polylog}(n)$ time) algorithm that takes as input a vertex $v \in V_n$ and an index $\ell$, and returns the $\ell$-th neighbor of $v$ (according to some order). This is the usual model considered for quantum Hamiltonian simulation with the graph's adjacency matrix $A_n$.

Regarding the confusion with wikipedia's definition of "implicitly defined": in CS/combinatorics, a graph family is called explicit if we can provide an algorithm to explicitly generate the graph (i.e., write it down in memory) in time $\mathrm{poly}(n)$. This is weaker than being strongly explicit. So the algorithm is an implicit description of the graph, and its description size could be much smaller than the memory size required to write down the full adjacency matrix/list explicitly (e.g., $\mathrm{polylog}(n)$ versus $\mathrm{poly}(n)$).