Solving systems of Boolean multivariate equations with quantum annealing

Understand

Polynomial systems over the binary field have important applications, especially in symmetric and asymmetric cryptanalysis, multivariate-based post-quantum cryptography, coding theory, and computer algebra.

• In this work, we study the quantum annealing model for solving Boolean systems of multivariate equations of degree 2, usually referred to as the Multivariate Quadratic problem.
• We present different methodologies to embed the problem into a Hamiltonian that can be solved by available quantum annealing platforms.
• In particular, we provide three embedding options, and we highlight their differences in terms of quantum resources.