Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

International Symposium on Computing and Networking Workshops (CANDARW)

Breaking SHA-1 through QUBO models

Shunsuke Tsukiyama, Koji Nakano, Yasuaki Ito, Takumi Kato, Yuya Kawamata

Published Nov 26, 2024• 0 citations
Publisher

Abstract

A Quadratic Unconstrained Binary Optimization (QUBO) model is defined by a quadratic objective function comprising binary variables, each taking values of 0 or 1. The objective of the QUBO problem is to determine the optimal assignment of these binary variables to minimize the QUBO model. QUBO models are instrumental in solving various combinatorial optimization problems, leading to extensive research on solver development, as many combinatorial optimization problems can be reformulated as QUBO problems. Notably, D-Wave Systems, a company specializing in quantum technologies, has developed quantum annealers which are programmable QUBO solvers that utilize quantum mechanics. SHA-1 is a cryptographic hash function that generates a 160-bit hash value from a message of an arbitrary length. This hash value makes it difficult to compute the original message within a practical timeframe. A pre-image attack, which aims to compute the original message from a hash value, is important in cryptographic hash functions. Previous research has shown that a QUBO can be designed to simulate SHA-1, facilitating the execution of a pre-image attack. In this paper, we present a novel QUBO model with fewer bits, linear terms, and quadratic terms than previous QUBO models for simulating hash values and pre-image calculations in SHA-1. While the previous QUBO model requires 34,016 bits, 32,584 linear terms, and 168,188 quadratic terms, our new model requires only 32,096 bits, 26,600 linear terms, and 157,308 quadratic terms. This approach can efficiently execute pre-image attacks using a quantum annealer, providing valuable insights for evaluating the robustness of cryptographic security systems.

DOI
10.1109/candarw64572.2024.00042

Related papers

CUBO-to-QUBO Conversion: Reducing Cubic Formulations to Quadratic Formulations

Shunsuke Tsukiyama, Xiaotian Li, Koji Nakano +5 more

Quadratic Unconstrained Binary Optimization (QUBO) models are defined by quadratic expressions composed of binary variables, each taking a value of either 0 or 1. The objective of the QUBO problem is to find an optimal assignment of these binary variables that minimizes the value of the QUBO model. The QUBO problem has attracted significant research interest due to its versatility in reformulating various NP-complete problems and its potential for efficiently finding heuristic solutions through quantum annealing. This paper focuses on converting Cubic Unconstrained Binary Optimization (CUBO) problems, defined by cubic expressions, into equivalent QUBO models. Through this conversion, CUBO problems can be solved using quantum annealing. Since the important NP-hard problem 3-SAT can be straightforwardly represented as a CUBO problem, investigating the conversion from CUBO to QUBO models is a meaningful endeavor.

IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum•Jun 3, 2025•1 citation

New QUBO Transformations to Improve Quantum and Simulated Annealing Performance for Quadratic Knapsack

Nicolás Borrajo, Juan Marcos Ramírez, Farzam Nosrati +3 more

Recent advancements in quantum computing have demonstrated significant potential for solving combinatorial optimization problems, like the quadratic knapsack problem, a constrained binary optimization problem. However, current quantum and quantum-inspired algorithms often require transforming these constrained problems into an unconstrained form, known as Quadratic Unconstrained Binary Optimization (QUBO). Such transformations can significantly impact the algorithms’ speed and efficiency. In this study, we evaluate five existing transformation methods and propose four novel approaches. We assess all nine methods using Simulated Annealing and find that three of our approaches outperform existing methods in terms of execution time and the quality and quantity of feasible solutions found. Additionally, we tested these transformations on quantum annealers, which were unable to solve even small problem instances, due to limitations in connectivity and error rates. However, our results highlight the advantages of the new approaches, which reduce the total number of variables in the QUBO representation. This is a critical factor for enhanced performance on emerging quantum hardware, since it also reduces the required number of qubits and the embedding chain lengths.

•Jan 1, 2026•0 citations

New QUBO Transformations to Improve Quantum and Simulated Annealing Performance for Quadratic Knapsack

Nicolás Borrajo, Juan Ramírez, Farzam Nosrati +3 more

Recent advancements in quantum computing have demonstrated significant potential for solving combinatorial optimization problems, like the quadratic knapsack problem, a constrained binary optimization problem. However, current quantum and quantum-inspired algorithms often require transforming these constrained problems into an unconstrained form, known as Quadratic Unconstrained Binary Optimization (QUBO). Such transformations can significantly impact the algorithms’ speed and efficiency. In this study, we evaluate five existing transformation methods and propose four novel approaches. We assess all nine methods using Simulated Annealing and find that three of our approaches outperform existing methods in terms of execution time and the quality and quantity of feasible solutions found. Additionally, we tested these transformations on quantum annealers, which were unable to solve even small problem instances, due to limitations in connectivity and error rates. However, our results highlight the advantages of the new approaches, which reduce the total number of variables in the QUBO representation. This is a critical factor for enhanced performance on emerging quantum hardware, since it also reduces the required number of qubits and the embedding chain lengths.

International Conference on Agents and Artificial Intelligence (ICAART)•Jan 1, 2026•1 citation

New QUBO Transformations to Improve Quantum and Simulated Annealing Performance for Quadratic Knapsack

Nicolás Borrajo Carro, Juan Marcos Ramírez, Farzam Nosrati +3 more

Recent advancements in quantum computing have demonstrated significant potential for solving combinatorial optimization problems, like the quadratic knapsack problem, a constrained binary optimization problem. How- ever, current quantum and quantum-inspired algorithms often require transforming these constrained problems into an unconstrained form, known as Quadratic Unconstrained Binary Optimization (QUBO). Such transfor- mations can significantly impact the algorithms’ speed and efficiency. In this study, we evaluate five existing transformation methods and propose four novel approaches. We assess all nine methods using Simulated An- nealing and find that three of our approaches outperform existing methods in terms of execution time and the quality and quantity of feasible solutions found. Additionally, we tested these transformations on quantum annealers, which were unable to solve even small problem instances, due to limitations in connectivity and error rates. However, our results highlight the advantages of the new approaches, which reduce the total num- ber of variables in the QUBO representation. This is a critical factor for enhanced performance on emerging quantum hardware, since it also reduces the required number of qubits and the embedding chain lengths.

•May 27, 2025•0 citations

QUBO Refinement: Achieving Superior Precision through Iterative Quantum Formulation with Limited Qubits

Hyunju Lee, Kyungtaek Jun

In the era of quantum computing, the emergence of quantum computers and subsequent advancements have led to the development of various quantum algorithms capable of solving linear equations and eigenvalues, surpassing the pace of classical computers. Notably, the hybrid solver provided by the D-wave system can leverage up to two million variables. By exploiting this technology, quantum optimization models based on quadratic unconstrained binary optimization (QUBO) have been proposed for applications, such as linear systems, eigenvalue problems, RSA cryptosystems, and CT image reconstruction. The formulation of QUBO typically involves straightforward arithmetic operations, presenting significant potential for future advancements as quantum computers continue to evolve. A prevalent approach in these developments is the binarization of variables and their mapping to multiple qubits. These methods increase the required number of qubits as the range and precision of each variable increase. Determining the optimal value of a QUBO model becomes more challenging as the number of qubits increases. Furthermore, the accuracies of the existing Qiskit simulator, D-Wave system simulator, and hybrid solver are limited to two decimal places. Problems arise because the qubits yielding the optimal value for the QUBO model may not necessarily correspond to the solution of a given problem. To address these issues, we propose a new iterative algorithm. The novel algorithm sequentially progresses from the highest to the lowest exponent in binarizing each number, whereby each number is calculated using two variables, and the accuracy can be computed up to a maximum of 16 decimal places.

arXiv:2411.16138•Nov 25, 2024•0 citations

Bit duplication technique to generate hard QUBO problems

Xiaotian Li, Koji Nakano, Yasuaki Ito +6 more

Quadratic Unconstrained Binary Optimization (QUBO) is a combinatorial optimization to find an optimal binary solution vector that minimizes the energy value defined by a quadratic formula of binary variables in the vector. The main contribution of this paper is to present the bit duplication technique, which can generate a hard QUBO problem from any QUBO problem so that their optimal solutions take the same energy value. The idea of the bit duplication technique is to duplicate bits and then to give constraints so that the corresponding two bits take the same binary values. By this technique, any QUBO problem with$n$bits is converted to a hard QUBO problem with$2n$bits. We use random QUBO problems and N-Queen QUBO problems for experiments. The performance of QUBO solvers including Gurobi optimizer, Fixstars Amplify AE, OpenJij with SA, D-Wave Hybrid solver, and ABS QUBO solver are evaluated for solving these QUBO problems. The experimental results show that generated QUBO problems by the bit duplication technique are much harder than the original QUBO problems. Hence, the bit duplication technique is a potent method to generate hard QUBO problems and generated QUBO problems can be used as benchmark problems for evaluating the search performance of QUBO solvers.

International Symposium on Computing and Networking Workshops (CANDARW)•Nov 1, 2022•2 citations
A Quadratic Unconstrained Binary Optimization (QUBO) model is defined by a quadratic objective function comprising binary variables, each taking values of 0 or 1. The objective of the QUBO problem is to determine the optimal assignment of these binary variables to minimize the QUBO model. QUBO models are instrumental in solving various combinatorial optimization problems, leading to extensive research on solver development, as many combinatorial optimization problems can be reformulated as QUBO problems. Notably, D-Wave Systems, a company specializing in quantum technologies, has developed quantum annealers which are programmable QUBO solvers that utilize quantum mechanics. SHA-1 is a cryptographic hash function that generates a 160-bit hash value from a message of an arbitrary length. This hash value makes it difficult to compute the original message within a practical timeframe. A pre-image attack, which aims to compute the original message from a hash value, is important in cryptographic hash functions. Previous research has shown that a QUBO can be designed to simulate SHA-1, facilitating the execution of a pre-image attack. In this paper, we present a novel QUBO model with fewer bits, linear terms, and quadratic terms than previous QUBO models for simulating hash values and pre-image calculations in SHA-1. While the previous QUBO model requires 34,016 bits, 32,584 linear terms, and 168,188 quadratic terms, our new model requires only 32,096 bits, 26,600 linear terms, and 157,308 quadratic terms. This approach can efficiently execute pre-image attacks using a quantum annealer, providing valuable insights for evaluating the robustness of cryptographic security systems.
Quadratic Unconstrained Binary Optimization (QUBO) models are defined by quadratic expressions composed of binary variables, each taking a value of either 0 or 1. The objective of the QUBO problem is to find an optimal assignment of these binary variables that minimizes the value of the QUBO model. The QUBO problem has attracted significant research interest due to its versatility in reformulating various NP-complete problems and its potential for efficiently finding heuristic solutions through quantum annealing. This paper focuses on converting Cubic Unconstrained Binary Optimization (CUBO) problems, defined by cubic expressions, into equivalent QUBO models. Through this conversion, CUBO problems can be solved using quantum annealing. Since the important NP-hard problem 3-SAT can be straightforwardly represented as a CUBO problem, investigating the conversion from CUBO to QUBO models is a meaningful endeavor.
Recent advancements in quantum computing have demonstrated significant potential for solving combinatorial optimization problems, like the quadratic knapsack problem, a constrained binary optimization problem. However, current quantum and quantum-inspired algorithms often require transforming these constrained problems into an unconstrained form, known as Quadratic Unconstrained Binary Optimization (QUBO). Such transformations can significantly impact the algorithms’ speed and efficiency. In this study, we evaluate five existing transformation methods and propose four novel approaches. We assess all nine methods using Simulated Annealing and find that three of our approaches outperform existing methods in terms of execution time and the quality and quantity of feasible solutions found. Additionally, we tested these transformations on quantum annealers, which were unable to solve even small problem instances, due to limitations in connectivity and error rates. However, our results highlight the advantages of the new approaches, which reduce the total number of variables in the QUBO representation. This is a critical factor for enhanced performance on emerging quantum hardware, since it also reduces the required number of qubits and the embedding chain lengths.
Recent advancements in quantum computing have demonstrated significant potential for solving combinatorial optimization problems, like the quadratic knapsack problem, a constrained binary optimization problem. However, current quantum and quantum-inspired algorithms often require transforming these constrained problems into an unconstrained form, known as Quadratic Unconstrained Binary Optimization (QUBO). Such transformations can significantly impact the algorithms’ speed and efficiency. In this study, we evaluate five existing transformation methods and propose four novel approaches. We assess all nine methods using Simulated Annealing and find that three of our approaches outperform existing methods in terms of execution time and the quality and quantity of feasible solutions found. Additionally, we tested these transformations on quantum annealers, which were unable to solve even small problem instances, due to limitations in connectivity and error rates. However, our results highlight the advantages of the new approaches, which reduce the total number of variables in the QUBO representation. This is a critical factor for enhanced performance on emerging quantum hardware, since it also reduces the required number of qubits and the embedding chain lengths.
Recent advancements in quantum computing have demonstrated significant potential for solving combinatorial optimization problems, like the quadratic knapsack problem, a constrained binary optimization problem. How- ever, current quantum and quantum-inspired algorithms often require transforming these constrained problems into an unconstrained form, known as Quadratic Unconstrained Binary Optimization (QUBO). Such transfor- mations can significantly impact the algorithms’ speed and efficiency. In this study, we evaluate five existing transformation methods and propose four novel approaches. We assess all nine methods using Simulated An- nealing and find that three of our approaches outperform existing methods in terms of execution time and the quality and quantity of feasible solutions found. Additionally, we tested these transformations on quantum annealers, which were unable to solve even small problem instances, due to limitations in connectivity and error rates. However, our results highlight the advantages of the new approaches, which reduce the total num- ber of variables in the QUBO representation. This is a critical factor for enhanced performance on emerging quantum hardware, since it also reduces the required number of qubits and the embedding chain lengths.
In the era of quantum computing, the emergence of quantum computers and subsequent advancements have led to the development of various quantum algorithms capable of solving linear equations and eigenvalues, surpassing the pace of classical computers. Notably, the hybrid solver provided by the D-wave system can leverage up to two million variables. By exploiting this technology, quantum optimization models based on quadratic unconstrained binary optimization (QUBO) have been proposed for applications, such as linear systems, eigenvalue problems, RSA cryptosystems, and CT image reconstruction. The formulation of QUBO typically involves straightforward arithmetic operations, presenting significant potential for future advancements as quantum computers continue to evolve. A prevalent approach in these developments is the binarization of variables and their mapping to multiple qubits. These methods increase the required number of qubits as the range and precision of each variable increase. Determining the optimal value of a QUBO model becomes more challenging as the number of qubits increases. Furthermore, the accuracies of the existing Qiskit simulator, D-Wave system simulator, and hybrid solver are limited to two decimal places. Problems arise because the qubits yielding the optimal value for the QUBO model may not necessarily correspond to the solution of a given problem. To address these issues, we propose a new iterative algorithm. The novel algorithm sequentially progresses from the highest to the lowest exponent in binarizing each number, whereby each number is calculated using two variables, and the accuracy can be computed up to a maximum of 16 decimal places.
Quadratic Unconstrained Binary Optimization (QUBO) is a combinatorial optimization to find an optimal binary solution vector that minimizes the energy value defined by a quadratic formula of binary variables in the vector. The main contribution of this paper is to present the bit duplication technique, which can generate a hard QUBO problem from any QUBO problem so that their optimal solutions take the same energy value. The idea of the bit duplication technique is to duplicate bits and then to give constraints so that the corresponding two bits take the same binary values. By this technique, any QUBO problem withnnnbits is converted to a hard QUBO problem with2n2n2nbits. We use random QUBO problems and N-Queen QUBO problems for experiments. The performance of QUBO solvers including Gurobi optimizer, Fixstars Amplify AE, OpenJij with SA, D-Wave Hybrid solver, and ABS QUBO solver are evaluated for solving these QUBO problems. The experimental results show that generated QUBO problems by the bit duplication technique are much harder than the original QUBO problems. Hence, the bit duplication technique is a potent method to generate hard QUBO problems and generated QUBO problems can be used as benchmark problems for evaluating the search performance of QUBO solvers.