4
$\begingroup$

I am reading a paper on Quantum Computing. What does it mean when authors says "$\log(m)$-qubits. I know what does $n$-qubit mean where $n$ is positive integer, but $\log(m)$ may not be an integer, in that case how would we define $\log(m)$ qubit.

https://www.researchgate.net/publication/348796217_Quantum_Bloom_filter_and_its_applications

enter image description here

$\endgroup$
3
  • 1
    $\begingroup$ It should probably say $\lceil\log_2(m)\rceil$ qubits. $\endgroup$ – DaftWullie Mar 5 at 13:29
  • 2
    $\begingroup$ It may be easier to say for certain if you provide a reference/link to the paper from which you took the screenshot. $\endgroup$ – Rammus Mar 5 at 13:31
  • $\begingroup$ @Rammus Kindly see the edited post. $\endgroup$ – A B Mar 5 at 13:33
5
$\begingroup$

Unfortunately the first answer by benrg is not correct: "$\log m$ qubits" in that sentence does not have to do with "asymptotic complexity" and the reason why floor and ceiling functions are left out is not because of them being equivalent asymptotically (even though they are equivalent asymptotically, it's not the reason why they left those symbols out here).

What is being described is an algorithm, and in step 4 of the algorithm, exactly $\log_2 m$ qubits are needed, not "$\mathcal{O}(\log_2 m)$ qubits" which means $\le C\log_2 m$ qubits for a positive constant $C$ and for sufficiently large $m$.

You can see later in the paper that the "first $\log_2 m$ qubits" are treated one way, and the "last $\log_2 m$ qubits" are treated another way:

"Furthermore, from Eqs.32, we can see that the first logm qubits are plain (i.e., the maximally mixed state), while the last logm qubits are obscure due to the secret 𝑟."

They also describe what happens to the "second $\log_2 m$ qubits" elsewhere.

It's just describing a specific number of qubits on which you're doing, for example, a measurement. This indicates that $m$ ought to be a power of 2 in the algorithm. You can read the algorithm in more detail and try it in full for small values of $m$ to get a feel for why that might be.

At the end of the paper they talk about the algorithm needing $\mathcal{O}(\log_2 m)$ qubits, but that's the total number of qubits required, which includes the "first" $\log_2 m$ qubits, the "second" $\log_2 m$ qubits, and the "last" $\log_2 m$ to which they referred. The authors did not forget a "big Oh" when they were talking about what to do to the "first" $\log_2 m$ qubits.

$\endgroup$
2
$\begingroup$

As DaftWullie said in a comment, $\log m$ is most likely a shorthand for $\lceil\log_2 m\rceil$.

Traditionally in computer science, one looks only at the asymptotic complexity of algorithms. Logarithms to different (constant) bases are asymptotically equivalent, so the base is usually omitted, and floor and ceiling operations don't affect the complexity, so they're usually left out.

Given the current state of quantum computing hardware, it would probably make sense to do a more careful analysis of the exact minimum qubit requirements of quantum algorithms, but old habits die hard.

$\endgroup$
2
  • $\begingroup$ Why "ceil", not "floor"? $\endgroup$ – Norbert Schuch Mar 5 at 20:59
  • $\begingroup$ Also, it would only make sense to make a more careful analysis if this is about outperforming things on current/near-term hardware. $\endgroup$ – Norbert Schuch Mar 5 at 21:00

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.