1
$\begingroup$

Many quantum-Fourier-transform-based quantum algorithms are based on the output probability distribution measurement.

But I'm wondering if this measurement is necessarily required for every quantum algorithm.

If required, doesn't it make the computing speed slow?

$\endgroup$

3 Answers 3

2
$\begingroup$

In order for the output of a quantum computer to be informative to you, you need to "look" at the result. The act of "looking", or "observation" is really some type of quantum measurement. Thus, any "useful" quantum algorithm will require measurement in some capacity.

Just like quantum gates, a measurement takes time as it involves interacting the system of interest with a measurement apparatus. So any measurements should be included in the cost of running an algorithm. Whether or not these measurements constitute a significant bottleneck depends on the quantum algorithm and physical apparatus under consideration.

$\endgroup$
2
  • $\begingroup$ Thank you for your comment. So what you are saying is that quantum algorithms that require computational basis measurement should measure the whole computational basis for looking at the result? $\endgroup$
    – William
    Jun 9, 2022 at 15:49
  • 1
    $\begingroup$ @William By "whole computational basis" I assume you mean measure every qubit? In fact, in many cases it is not necessary or desirable to measure every qubit. What I am saying is that a "useful" quantum circuit must contain at least one measurement on some part of the circuit (i.e. at least one qubit). $\endgroup$
    – Jacob
    Jun 10, 2022 at 20:22
2
$\begingroup$

A quantum state can't affect the wider world unless a measurement is performed, so in order for a quantum computation to be useful it must ultimately lead to or contribute to a measurement somewhere.

That being said, there are many quantum algorithms that transform quantum information, without measuring it, as part of some larger algorithm. Examples include subroutines like amplitude amplifications, the quantum fourier transform, reversible arithmetic operations, and magic state preparation.

An interesting corner case is catalysis, where a specific helper state is needed for an operation to work but the state is restored by the end of the operation. The state is not doing anything it just goes into and out of the operation unchanged, so how could the state be affecting any measurement? And yet if you change the state the operation will go wrong, which is ultimately revealed by measurements later returning different results.

$\endgroup$
0
$\begingroup$

Most quantum algorithms uses output probability distribution measurement and therefore many shots. However the running time of an quantum algorithm is very short say a 1 ms. Even with 1000 shots the total time is still small. In the quantum supremacy experiment of Google it took 200 seconds to calculate a problem that a classical computer will take years to solve.

$\endgroup$
1
  • $\begingroup$ Thank you for your comment. But in some cases, due to the cross talk in the case of ion trap or low photon number in optics, the measurement takes a lot of time these days. Also, due to the lack of equipments, the randomized computational basis measurement is difficult in university-level experiments. Even in this case, can we say that quantum computing has an advantage over classical computers? Or do we need to just see them as demonstration? It seems like most quantum computing demonstration published in Nature or Science is very slow these days, except those quantum supremacy experiments. $\endgroup$
    – William
    Jun 9, 2022 at 13:04

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.