Content deleted Content added
m →Adjacency matrix model: Typo fixing, replaced: directed directed → directed |
m →Quantum query complexity of certain types of graph problems: wikistyle table titles and \log |
||
Line 92:
{| class="wikitable"
|+
Quantum
!Problem
!Matrix
!Array
|-
|Minimum Spanning Tree
Line 107:
|Strong Connectivity
|<math>\Theta(n^{3/2})</math>
|<math>\Omega(\sqrt{nm})</math>, <math>O(\sqrt{
|-
|Single Source Shortest Path
|<math>\Omega(n^{3/2})</math>, <math>O(n^{3/2}\log^2n)</math>
|<math>\Omega(\sqrt{nm})</math>, <math>O(\sqrt{nm}\log^2(n))</math>
|}
Notice the discrepancy between the quantum query complexities associated with a particular type of problem, depending on which query model was used to determine the complexity. For example, when the matrix model is used, the quantum complexity of the connectivity model in [[Big O notation]] is <math>\Theta(n^{3/2})</math>, but when the array model is used, the complexity is <math>\Theta(n)</math>. Additionally, for brevity, we use the shorthand <math>m</math> in certain cases, where <math>m=\Theta(n^2)</math>.<ref name=":0" /> The important implication here is that the efficiency of the algorithm used to solve a graphing problem is dependent on the type of query model used to model the graph.
| |||