Limitations of Quantum Methods for Breaking Cryptography and for Optimization

Abstract

The development of quantum computers raises fundamental questions about the extent to which quantum algorithms can outperform classical methods. This thesis studies limitations of quantum methods in two domains: symmetric-key cryptography and combinatorial optimization.

The first part of the thesis investigates the post-quantum security of block-cipher-based constructions. We obtain the first post-quantum security proofs for several important symmetric-key primitives, including the key-length extension scheme \fx, the tweakable block ciphers \lrw, and a broad class of block-cipher modes. Our results show that quantum adversaries with limited quantum oracle access do not achieve attacks substantially stronger than those captured by tight classical bounds.

The thesis also studies permutation inversion in the quantum query model, proving lower bounds showing that the problem remains essentially as hard as standard inversion even with inverse access or quantum advice. These results highlight fundamental barriers to quantum speedups that are independent of specific cryptographic constructions.

Finally, we study multiangle \qaoa and show numerically that exploiting problem symmetries can reduce parameter complexity while preserving most of the algorithm’s performance, although the extent and generality of such reductions are inherently limited. This study provides insight into both the potential and the limitations of quantum optimization algorithms.