Quantum complexity theory: Difference between revisions

Revision as of 08:03, 1 September 2021

Revision as of 08:04, 1 September 2021

Line 86:

==== Adjacency array model ====

Next, there is the slightly more complicated adjacency array model built on the idea of [[adjacency list]]s, 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 ===