Quantum complexity theory: Difference between revisions

Revision as of 03:26, 23 November 2020

Revision as of 03:30, 23 November 2020

Line 83:

|<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 single source shortest pathconnectivity model in [[Big O notation]] is <math>\OmegaTheta(n^{3/2})</math>, but when the array model is used, the complexity is <math>\OmegaTheta(\sqrt{nm}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.

=== Other Types of Quantum Computational Queries ===