Optimization by decoded quantum interferometry

Area of Science:

• Quantum computing
• Computational complexity
• Algorithm development

Background:

• Achieving superpolynomial speed-ups for optimization problems is a key goal in quantum algorithm research.
• Classical optimization algorithms face limitations in solving complex problems efficiently.

Purpose of the Study:

• Introduce decoded quantum interferometry (DQI) as a novel quantum algorithm for optimization.
• Investigate the potential of DQI to achieve superpolynomial speed-ups.
• Explore DQI's applicability to optimization problems with and without algebraic structure.

Main Methods:

• Developed decoded quantum interferometry (DQI), a quantum algorithm utilizing the quantum Fourier transform.
• Reduced optimization problems to decoding problems, leveraging algebraic structures.
• Applied DQI to approximate polynomial fits over finite fields.
• Investigated DQI for sparse clause optimization problems, reducing them to decoding low-density parity-check codes.

Main Results:

• DQI achieves superpolynomial speed-ups for approximating optimal polynomial fits over finite fields.
• DQI demonstrates substantial speed-ups for a max-XORSAT instance compared to classical heuristics.
• The quantum Fourier transform combined with decoding primitives shows promise for quantum speed-ups.

Conclusions:

• Decoded quantum interferometry (DQI) presents a promising new avenue for quantum speed-ups in optimization.
• The approach effectively leverages algebraic structures and decoding primitives for enhanced performance.
• Further research can explore DQI's potential for a wider range of hard optimization problems.