2
$\begingroup$

In other words, if an algorithm requires N total calls to the quantum computer to find the solution (of any given problem), would N be equivalent to its query complexity?

$\endgroup$
2
$\begingroup$

The query complexity is usually spoken about with respect to an oracle or black-box function. It is the numbers of times you make use of that oracle in your algorithm (each time you use it, you are said to be "querying it", hence the terminology "query complexity"). It might be that you use the oracle many times in a single run of the algorithm on the quantum computer (such as in Grover's search).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.