<p>Yes! But I can see why it is confusing.</p>
<p>A <em>strongly explicit</em> graph family <span class="math-container">$\{G_n = (V_n,E_n)\}$</span> (parameterized e.g. by number of vertices <span class="math-container">$n$</span>) is described by an efficient (<span class="math-container">$\mathrm{polylog}(n)$</span> time) algorithm that takes as input a vertex <span class="math-container">$v \in V_n$</span> and an index <span class="math-container">$\ell$</span>, and returns the <span class="math-container">$\ell$</span>-th neighbor of <span class="math-container">$v$</span> (according to some order). This is the usual model considered for quantum Hamiltonian simulation with the graph's adjacency matrix <span class="math-container">$A_n$</span>.</p>
<p>Regarding the confusion with wikipedia's definition of &quot;implicitly defined&quot;: in CS/combinatorics, a graph family is called <em>explicit</em> if we can provide an algorithm to explicitly generate the graph (i.e., write it down in memory) in time <span class="math-container">$\mathrm{poly}(n)$</span>. This is weaker than being <em>strongly</em> explicit. So the algorithm is an <em>implicit</em> 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., <span class="math-container">$\mathrm{polylog}(n)$</span> versus <span class="math-container">$\mathrm{poly}(n)$</span>).</p>

CC BY-SA 4.0
2023-07-17T09:11:18.773Z
2023-07-17T09:11:18.773Z
smapers
<p>There seems to be a slight difference in terminology among a couple of different traditions within theoretical computer science.</p>
<ul>
<li>To have a quantum computer <a href="https://en.wikipedia.org/wiki/Hamiltonian_simulation" rel="nofollow noreferrer">simulate the Hamiltonian evolution</a> of <span class="math-container">$\exp(-iAt)$</span> of some <span class="math-container">$2^n\times 2^n$</span> hermitian matrix <span class="math-container">$A$</span> giving the adjacency matrix of a sparse undirected graph on <span class="math-container">$2^n$</span> 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 <span class="math-container">$A$</span> with edge-colors and subsequently Trotterize the partition;</li>
<li>In the theory of expanders, as explained by O'Donnell <a href="https://www.cs.cmu.edu/%7Eodonnell/toolkit13/lecture12.pdf" rel="nofollow noreferrer">here</a> 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 <em>explicit</em> family of graphs.  But, when we are also provided oracular access to adjacent vertices, this has been referred to as a <em><strong>strongly explicit</strong></em> family of expanders; while</li>
<li>Wikipedia <a href="https://en.wikipedia.org/wiki/Implicit_graph" rel="nofollow noreferrer">defines</a> an <em><strong>implicit</strong></em> 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.</li>
</ul>
<p>It's these last two terms that I'm wondering about - is it correct to say that an <strong>implicitly defined</strong> graph could be a member of a <strong>strongly explicit</strong> family of expanders (and, if so, could it be amenable to Hamiltonian simulation)?</p>

<quantum-computing><terminology><expanders><sparse-matrix>
Could an *implicitly* defined graph be a member of a *strongly-explicit* family of expanders?
Mark S
# Could an *implicitly* defined graph be a member of a *strongly-explicit* family of expanders?

(Asked by: username_0 on 2023-07-16)

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](https://en.wikipedia.org/wiki/Hamiltonian_simulation) 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](https://www.cs.cmu.edu/%7Eodonnell/toolkit13/lecture12.pdf) 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](https://en.wikipedia.org/wiki/Implicit_graph) 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)?

**Tags:** quantum-computing, terminology, expanders, sparse-matrix


---

## 1 answers

### Answer by username_1 on 2023-07-17. Score: 1 | Accepted answer

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)$).


---

