Content deleted Content added
→Quantum Query Complexity of Certain Types of Graph Problems: Updated some formulas, and reworded a few things for clarity |
Tags: Reverted Visual edit |
||
Line 58:
Next, there is the slightly more complicated adjacency array model built on the idea of [[Adjacency list|adjacency lists]], where every vertex, <math>u </math>'','' is associated with an array of neighboring vertices such that <math>f_i:[d_i^+]\rightarrow[n] </math>, for the out-degrees of vertices <math>d_i^+,...,d_n^+ </math>, where <math>n </math> is the minimum value of the upper bound of this model, and <math>f_i(j) </math> returns the "<math>j^{th} </math>" vertex adjacent to <math>i </math>. Additionally, the adjacency array model satisfies the simple graph condition, <math>\forall i\in[n],j,j^{'}\in[k],j\neq j^{'}: f_i(j)\neq f_i(j^{'}) </math>, meaning that there is only one edge between any pair of vertices, and the number of edges is minimized throughout the entire model (see [[Spanning tree]] model for more background). <ref name=":0" />
==== Quantum Query Complexity of Certain Types of Graph Problems ====
Both of the above models can be used to determine the query complexity of particular types of graphing problems, including the [[Connectivity (graph theory)|connectivity]], [[Strongly connected component|strong connectivity]] (a directed graph version of the connectivity model), [[minimum spanning tree]], and [[Shortest path problem|single source shortest path]] models of graphs. An important caveat to consider is that the quantum complexity of a particular type of graphing problem can change based on the query model (namely either matrix or array) used to determine the solution. The following table showing the quantum query complexities of these types of graphing problems illustrates this point well.
{| class="wikitable"
| |||