1
$\begingroup$

It looks like in a lot of quantum algorithms, we use the quantum query model. I wanted to know what are the other types of models of computation, used in quantum computing as well as in classical computing?

On what model of computation are algorithms (such as Binary Search, Sorting, etc.) based?

$\endgroup$
3
  • 1
    $\begingroup$ Binary search is an algorithm and sorting is a class of algorithms (e.g. bubble sort, quick sort), could you clarify what you mean by model? Do you mean types of algorithms? $\endgroup$
    – epelaaez
    Jun 16 '21 at 13:43
  • $\begingroup$ And by query model I guess you refer to those algorithms that make use of a black box oracle, right? So maybe other types are Grover’s algorithm where we use amplitude amplification and Shor’s where we use phase estimation. $\endgroup$
    – epelaaez
    Jun 16 '21 at 13:47
  • $\begingroup$ Hey @epelaaez , I meant that since a lot of quantum algorithm like Grover search make use of oracle, they query the input a certain number of times depending on input so is that the case with algorithm such as Binary Search do ( like in binary search we consider the middle elements and we approximately take log(n) elements by the end where n is the size of array). So, do we use oracle for accessing input in such algorithm as well ? I mean does Binary Search uses oracle? Also, do the classical and quantum algorithms both work on circuit model? $\endgroup$
    – Noob
    Jun 16 '21 at 14:35
1
$\begingroup$

So, do we use oracle for accessing input in such algorithm as well?

As for this question, an oracle in quantum computing is different from accesing an array in classical computing. This is because quering an oracle in quantum computing implies computing a function for a certain input. And many times there are no efficient ways to compute these functions, which is why the query model (as you call it) is sometimes criticized. One of the main forms of a quantum oracle is

$$ U|x, 0\rangle = |x, f(x)\rangle, $$

where $f(x)$ is the function to compute. In query complexity theory, consulting an oracle is regarded as constant and is the measure of complexity. For example, Grover's algorithm's complexity is $O(\sqrt{N})$. However, if the function implemented by the oracle is too complicated, this may become too complex and the computational advantage may be lost.

Why is this different from classical computing? Accesing an array actually takes constant time. This is because what you are looking for is not computed at the moment, it is already stored in memory and can be accesed in constant time.

Also, do the classical and quantum algorithms both work on circuit model?

Yes, both models of computation have a circuit representation. Of course, complex classical programs are not depicted as circuits because they use millions of gates and bits. But you can look at an adder or other simple circuits in this model. For more about the circuit model of classical computation I recommend the book "Code: The Hidden Language of Computer Hardware and Software". It's from 1999 but the concepts are the same as today.

Now for quantum computing. The circuit/gate model is the most commonly used one. In this case, many algorithms (at least at the pedagogical level) don't take thousands of gates or qubits and therefore can be nicely visualized this way. For example, the Bell state circuit:

enter image description here

But there is another type of quantum computing called quantum annealing. This is the model used by D-Wave. This model is used with problems that have a discrete search space and many local minima. And the goal is finding the global minimum of this function. I cannot tell you a lot about how this works because I'm not familiarized with this model, but check out What is Quantum Annealing? by D-Wave.

There are other models, such as the measurement based model, adiabatic model (related to quantum annealing), topological model and quantum walk model. I'll give you some references for these models:

$\endgroup$
6
  • $\begingroup$ Hey, Thanks for the answer . Could you provide me a reference where I could learn query complexity ? $\endgroup$
    – Noob
    Jun 16 '21 at 19:15
  • $\begingroup$ @Noob check the query complexity section here. $\endgroup$
    – epelaaez
    Jun 16 '21 at 19:35
  • $\begingroup$ Does Binary Search, Sorting algorithms etc. all uses Query model? @epelaaez $\endgroup$
    – Noob
    Jun 18 '21 at 11:26
  • $\begingroup$ @Noob well, both of them are classical algorithms and the query model is for quantum computing, so they don’t use it $\endgroup$
    – epelaaez
    Jun 18 '21 at 13:40
  • $\begingroup$ But we do have a classical query model right? $\endgroup$
    – Noob
    Jun 18 '21 at 15:19

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.