3 ms·
Ask HN: Is “ignore constant” in complexity theory a scam?
In quantum system, the problem size grow by the exponential of 2. If the algorithm requires N qubits, the cost is O(2^N).
Say you invented a new algorithm. Required qubit is now N -> (N-3) [1]. By the 2^N rule, we see that this is equivalent to 2^3 = 8 times faster. O(0.125 2^N). This is the kind of major breakthrough in the field.
Often I reimplement someone else' code and got 20X~50X speed up. The speed is equivalent to lowering qubit requirement by 5.
But complexity theory tell us this speed up doesn't matter since constant term is ignored.
[1] Tapering-off qubit requirement by IBM lab
- Bimos 3y agoIn the last 25 years, algorithmic advances in integer optimization coupled with hardware improvements have resulted in an astonishing 800 billion factor speedup in mixed-integer optimization (MIO).[1] Still, it is just a constant. [1] https://dspace.mit.edu/handle/1721.1/110328 https://dspace.mit.edu/handle/1721.1/110328
- pestatije 3y agofor the purposes of complexity theory it isn't, however if you extrapolate the theory one-for-one to your algorithm and data then obviously its not going to work