Quantum Speedup on Limited Hamming Weight Simon's Problem

Many quantum algorithms have been theoretically shown to outperform their classical counterparts in solving problems of increasing size. However, in today's noisy intermediate-scale quantum (NISQ) devices, it is still difficult to demonstrate practical speedup in quantum computers (QCs) due to noise that leads to computational errors. Here, we demonstrate an algorithmic speedup for Simon's problem for oracles with Hamming weight (HW) up to 8 using the number-of-oracle-queries-to-solution (NTS) metric, which scales with problem size. The experiments were performed on two different 127-qubit IBM Quantum superconducting processors. The speedup on HW up to 7 is observed on ibm\_sherbrooke only when the computation is protected by dynamical decoupling (DD) and measurement error mitigation (MEM) is used to simulate the absence of measurement errors.