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

arXiv:2308.09704 · Future Generation Computer Systems

Generating hard Ising instances with planted solutions using post-quantum cryptographic protocols

Salvatore Mandrà, Humberto Munoz-Bauza, Gianni Mossi, Eleanor Gilbert Rieffel

Published Jan 22, 2025• 7 citations
arXivHTMLPDF
DOI
10.1016/j.future.2025.107721

Related papers

Increasing the hardness of posiform planting using random QUBOs for programmable quantum annealer benchmarking

Elijah Pelofske, Georg Hahn, Hristo N. Djidjev

Abstract Posiform planting is a method for constructing QUBO instances with a unique planted solution that can be tailored to arbitrary connectivity graphs. In this study we investigate making posiform planted QUBOs computationally harder by fusing many smaller random Ising models, whose global minimum is computed classically, with posiform planted QUBOs. The unique ground state of the resulting QUBO is the concatenation of (exactly one of) the ground states of each smaller problem. Our method generates QUBO instances that have a unique solution, are native to the hardware graph, and have tunable computational hardness. We use our QUBOs to benchmark three D-Wave quantum annealing processors (with 563–5627 qubits), and compare them against simulated annealing and Gurobi. Surprisingly, we find that the D-Wave ground state sampling success rate is not dependent on the glued random QUBO size, and that some QUBO classes are solved at high success rates at short annealing times on the Zephyr processors.

arXiv:2411.03626•npj Unconventional Computing•Jul 23, 2025•2 citations

CRYPTOGRAPHIC ALGORITHMS ON THE WAY TO POST-QUANTUM CRYPTOGRAPHY

Pavel Nikolaevich Nasedkin, Vladimir Aleksandrovich Sverkunov

Information Technology and Mathematical Modeling in the Management of Complex Systems•Jan 1, 2022•0 citations

Solving Prime Factorization Using Quantum Ising Model

Wen-Li Wang, Mei-Huei Tang, Shahid Hussain +1 more

Communications in computer and information science•Jan 1, 2026•1 citation

Posiform planting: generating QUBO instances for benchmarking

Georg Hahn, Elijah Pelofske, Hristo N. Djidjev

We are interested in benchmarking both quantum annealing and classical algorithms for minimizing quadratic unconstrained binary optimization (QUBO) problems. Such problems are NP-hard in general, implying that the exact minima of randomly generated instances are hard to find and thus typically unknown. While brute forcing smaller instances is possible, such instances are typically not interesting due to being too easy for both quantum and classical algorithms. In this contribution, we propose a novel method, called posiform planting, for generating random QUBO instances of arbitrary size with known optimal solutions, and use those instances to benchmark the sampling quality of four D-Wave quantum annealers utilizing different interconnection structures (Chimera, Pegasus, and Zephyr hardware graphs) and the simulated annealing algorithm. Posiform planting differs from many existing methods in two key ways. It ensures the uniqueness of the planted optimal solution, thus avoiding groundstate degeneracy, and it enables the generation of QUBOs that are tailored to a given hardware connectivity structure, provided that the connectivity is not too sparse. Posiform planted QUBOs are a type of 2-SAT boolean satisfiability combinatorial optimization problems. Our experiments demonstrate the capability of the D-Wave quantum annealers to sample the optimal planted solution of combinatorial optimization problems with up to 5, 627 qubits.

arXiv:2308.05859•Frontiers in Computer Science•Nov 21, 2023•4 citations

Post-quantum Cryptography: A Solution to the Challenges of Classical Encryption Algorithms

Shagun Sharma, K. R. Ramkumar, Amanpreet Kaur +3 more

Lecture notes in electrical engineering•Jan 1, 2023•36 citations

Benchmarking the optimization of optical machines with the planted solutions

Nikita Stroev, Natalia G. Berloff, Nir Davidson

This research focuses on developing effective benchmarks for quadratic unconstrained binary optimization instances, crucial for evaluating the performance of Ising hardware and solvers. Currently, the field lacks accessible and reproducible models for systematically testing such systems, particularly in terms of detailed phase space characterization. Here, we introduce universal generative models based on an extension of Hebb’s rule of associative memory with asymmetric pattern weights. We conduct comprehensive calculations across different scales and dynamical equations, examining outcomes like the probabilities of reaching the ground state, planted state, spurious state, or other energy levels. Additionally, the generated problems reveal properties such as the easy-hard-easy complexity transition and complex solution cluster structures. This method offers a promising platform for analyzing and understanding the behavior of physical hardware and its simulations, contributing to future advancements in optimization technologies. The authors present a method for creating generative models that produce test instances for quadratic unconstrained binary optimization (QUBO) problems, inspired by Hebb’s rule. Their approach identifies key solution patterns and complexity transitions, providing a platform to evaluate the performance of Ising hardware and solvers efficiently.

Communications Physics•Nov 19, 2024•1 citation
Abstract Posiform planting is a method for constructing QUBO instances with a unique planted solution that can be tailored to arbitrary connectivity graphs. In this study we investigate making posiform planted QUBOs computationally harder by fusing many smaller random Ising models, whose global minimum is computed classically, with posiform planted QUBOs. The unique ground state of the resulting QUBO is the concatenation of (exactly one of) the ground states of each smaller problem. Our method generates QUBO instances that have a unique solution, are native to the hardware graph, and have tunable computational hardness. We use our QUBOs to benchmark three D-Wave quantum annealing processors (with 563–5627 qubits), and compare them against simulated annealing and Gurobi. Surprisingly, we find that the D-Wave ground state sampling success rate is not dependent on the glued random QUBO size, and that some QUBO classes are solved at high success rates at short annealing times on the Zephyr processors.
We are interested in benchmarking both quantum annealing and classical algorithms for minimizing quadratic unconstrained binary optimization (QUBO) problems. Such problems are NP-hard in general, implying that the exact minima of randomly generated instances are hard to find and thus typically unknown. While brute forcing smaller instances is possible, such instances are typically not interesting due to being too easy for both quantum and classical algorithms. In this contribution, we propose a novel method, called posiform planting, for generating random QUBO instances of arbitrary size with known optimal solutions, and use those instances to benchmark the sampling quality of four D-Wave quantum annealers utilizing different interconnection structures (Chimera, Pegasus, and Zephyr hardware graphs) and the simulated annealing algorithm. Posiform planting differs from many existing methods in two key ways. It ensures the uniqueness of the planted optimal solution, thus avoiding groundstate degeneracy, and it enables the generation of QUBOs that are tailored to a given hardware connectivity structure, provided that the connectivity is not too sparse. Posiform planted QUBOs are a type of 2-SAT boolean satisfiability combinatorial optimization problems. Our experiments demonstrate the capability of the D-Wave quantum annealers to sample the optimal planted solution of combinatorial optimization problems with up to 5, 627 qubits.
This research focuses on developing effective benchmarks for quadratic unconstrained binary optimization instances, crucial for evaluating the performance of Ising hardware and solvers. Currently, the field lacks accessible and reproducible models for systematically testing such systems, particularly in terms of detailed phase space characterization. Here, we introduce universal generative models based on an extension of Hebb’s rule of associative memory with asymmetric pattern weights. We conduct comprehensive calculations across different scales and dynamical equations, examining outcomes like the probabilities of reaching the ground state, planted state, spurious state, or other energy levels. Additionally, the generated problems reveal properties such as the easy-hard-easy complexity transition and complex solution cluster structures. This method offers a promising platform for analyzing and understanding the behavior of physical hardware and its simulations, contributing to future advancements in optimization technologies. The authors present a method for creating generative models that produce test instances for quadratic unconstrained binary optimization (QUBO) problems, inspired by Hebb’s rule. Their approach identifies key solution patterns and complexity transitions, providing a platform to evaluate the performance of Ising hardware and solvers efficiently.