# A compact QUBO encoding of computational logic formulae demonstrated on cryptography constructions

Source: [A compact QUBO encoding of computational logic formulae demonstrated on cryptography constructions](<https://www.sota2.com/research/paper/68fa47e61e209131ce92ba32>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2026-04-17T05:00:13.532Z

Authors: Gregory Morse, Tam\\'as Kozsik, Oskar Mencer, Peter Rakyta

Published: 2024-09-10T18:46:26.000Z

## Abstract

We aim to advance the state-of-the-art in Quadratic Unconstrained Binary Optimization formulation with a focus on cryptography algorithms. As the minimal QUBO encoding of the linear constraints of optimization problems emerges as the solution of integer linear programming (ILP) problems, by solving special boolean logic formulas (like ANF and DNF) for their integer coefficients it is straightforward to handle any normal form, or any substitution for multi-input AND, OR or XOR operations in a QUBO form. To showcase the efficiency of the proposed approach we considered the most widespread cryptography algorithms including AES-128/192/256, MD5, SHA1 and SHA256. For each of these, we achieved QUBO instances reduced by thousands of logical variables compared to previously published results, while keeping the QUBO matrix sparse and the magnitude of the coefficients low. In the particular case of AES-256 cryptography function we obtained more than 8x reduction in variable count compared to previous results. The demonstrated reduction in QUBO sizes notably increases the vulnerability of cryptography algorithms against future quantum annealers, capable of embedding around $30$ thousands of logical variables.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

- [QUBO Encoding on AES-128](<https://www.sota2.com/research/sota/qubo-encoding-on-aes-128.md>): QUBO Encoding; AES-128; QUBO Size: 22802.

- [QUBO Encoding on MD5](<https://www.sota2.com/research/sota/qubo-encoding-on-md5.md>): QUBO Encoding; MD5; QUBO Size: 15320.

- [QUBO Encoding on SHA1](<https://www.sota2.com/research/sota/qubo-encoding-on-sha1.md>): QUBO Encoding; sha1; QUBO Size: 19426.

- [QUBO Encoding on SHA-256](<https://www.sota2.com/research/sota/qubo-encoding-on-sha-256.md>): QUBO Encoding; SHA-256; QUBO Size: 42899.

- [QUBO Encoding on AES-192](<https://www.sota2.com/research/sota/qubo-encoding-on-aes-192.md>): QUBO Encoding; AES-192; QUBO Size: 24264.

- [QUBO Encoding on AES-192 Decryption](<https://www.sota2.com/research/sota/qubo-encoding-on-aes-192-decryption.md>): QUBO Encoding; AES-192 Decryption; QUBO Size: 25959.

- [QUBO Encoding on AES-256](<https://www.sota2.com/research/sota/qubo-encoding-on-aes-256.md>): QUBO Encoding; AES-256; QUBO Size: 29330.

- [QUBO Encoding on AES-256 Decryption](<https://www.sota2.com/research/sota/qubo-encoding-on-aes-256-decryption.md>): QUBO Encoding; AES-256 Decryption; QUBO Size: 31242.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/2409.07501>)

[PDF](<https://arxiv.org/pdf/2409.07501.pdf>)
