1
$\begingroup$

From what I understood, quantum programming can solve some algorithm exponentially faster.

Thanks to the superposition, unlike a classic bit, which can be either 0 or 1, a qubit can be both 0 and 1.

Does that mean we can apply an algorithm for all bits possibly in one shot?

Example: We have 2 qubits, we apply a Hadamard gate on it to be in superposition. So all possibility will be [00, 01, 10, 11], so [0, 1, 2, 3]

Can we apply an algorithm for all of these solutions ?

For example, apply *10 to the value. So we would get [0, 10, 20, 30]. Then sum it all to get 60. But, getting that in one shot ?

I tried to implement something similar on Qiskit. Creating 2 qubits, applying Hadamard gate on them. But I fail to go further. If I measure my qubits, they will be one of the solutions, but not all of them.

Am I missing something ?

$\endgroup$
1

1 Answer 1

4
$\begingroup$

No, you're not missing something. Talking about being able to apply an algorithm for all possible inputs in a single shot is misleading. As you've found, you cannot read out all those answers; you can only get one answer, just as you would with classical.

The trick of quantum computing is asking the right question. This is typically some sort of comparison between the different values you've evaluated. You access it by performing some sort of interference between your multiple parallel evaluations, usually using something like a Hadamard transform or Fourier transform. Working out what that might be for a specific calculation you might want is the major challenge of algorithm design.

For the case that you're asking about, I believe there's a version of Grover's algorithm which you can use to calculate the average value of a function. It's far from single shot, but can provide a mild improvement in run time for large input sizes.

$\endgroup$
3
  • $\begingroup$ Thank you for the clear explanation. Is there some more algorithm that are "easy" to understand, and that are better/faster in quantum than classic computer. I saw Deutsch Jozsa Algorithm for example, do you have great other example that I could learn around ? $\endgroup$
    – Globy
    Apr 28, 2022 at 11:40
  • $\begingroup$ When I'm teaching, I usually go through the sequence Deutsch - Bernstein-Vazirani - Simon - Grover. There's not a huge number of accessible examples to work with! $\endgroup$
    – DaftWullie
    Apr 28, 2022 at 11:46
  • $\begingroup$ Awesome, I will look at those! Thanks for the help and the clear explanations $\endgroup$
    – Globy
    Apr 28, 2022 at 12:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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