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

Electronic colloquium on computational complexity

Generating Hard Instances of Lattice Problems

Miklós Ajtai

Published Jan 1, 1996• 598 citations
OpenAlex

Related papers

New (and Old) Proof Systems for Lattice Problems

Navid Alamati, Chris Peikert, Noah Stephens-Davidowitz

Lecture notes in computer science•Jan 1, 2018•11 citations

QUBO問題の複雑さに関する研究

LI XIAOTIAN

Quadratic Unconstrained Binary Optimization (QUBO) is a combinatorial optimization problem defined by an energy function that consists of a quadratic formula involving multiple binary variables.The goal of the QUBO problem is to find an optimal assignment of values to the variables that minimizes the energy function.With the increasing applicability of QUBO problems, QUBO solvers on different computing platforms have been developed.It is necessary to generate hard QUBO instances for improving and evaluating the performance of QUBO solvers.In this dissertation, we research in generating hard QUBO instances.First, we propose an effective method called bit duplication technique for generating hard QUBO instances with adjustable sizes.The idea is to duplicate specified number of 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 (n + m) bits (0 < m ≤ n).Second, in order to avoid the increase in the original size after performing bit duplication technique, we propose a novel technique which we call bit reduction to reduce the size of the original QUBO problem before preforming bit duplication technique.Through this method, hard QUBO instances can be generated without increasing the size of the original QUBO problem.By combining the bit duplication and bit reduction technique, we propose the method for generating hard instance of QUBO problems from any original QUBO problem without changing the size. 1 We use random QUBO problems, N-Queens problems, Traveling Salesman Problem (TSP), maximum weight matching (MWM) problems and Satisfiability problems (SAT) as original QUBO problems to generate hard QUBO instances.The performance of QUBO solvers including Gurobi optimizer, Fixstars Amplify AE, OpenJij with SA, D-Wave Hybrid and ABS2 QUBO solvers are evaluated for solving the generated hard QUBO instances.The experimental results show that generated QUBO instances are much hard for solving.

•Mar 23, 2025•0 citations

Comparing the hardness of MAX 2-SAT problem instances for quantum and classical algorithms

Puya Mirkarimi, Adam Callison, Lewis Light +2 more

An algorithm for a particular problem may find some instances of the problem easier and others harder to solve, even for a fixed input size. We numerically analyze the relative hardness of MAX 2-SAT problem instances for various continuous-time quantum algorithms and a comparable classical algorithm. This has two motivations: To investigate whether small-sized problem instances, which are commonly used in numerical simulations of quantum algorithms for benchmarking purposes, are a good representation of larger instances in terms of their hardness to solve, and to determine the applicability of continuous-time quantum algorithms in a portfolio approach, where we take advantage of the variation in the hardness of instances between different algorithms by running them in parallel. We find that, while there are correlations in instance hardness between all of the algorithms considered, they appear weak enough that a portfolio approach would likely be desirable in practice. Our results also show a widening range of hardness of randomly generated instances as the problem size is increased, which demonstrates both the difference in the distribution of hardness at small sizes and the value of a portfolio approach that can reduce the number of extremely hard instances. We identify specific weaknesses of these quantum algorithms that can be overcome with a portfolio approach, such their inability to efficiently solve satisfiable instances (which is easy classically).

arXiv:2206.06876•Physical Review Research•Jun 5, 2023•9 citations

Inapproximability Results for Computational Problems on Lattices

Subhash Khot

Information security and cryptography•Jan 1, 2009•21 citations

Quantum Lattice Problems

Hans A. De Raedt, Wolfgang von der Linden

Topics in applied physics•Jan 1, 1992•5 citations

Identifying hard native instances for the maximum-independent-set problem on neutral-atom quantum processors

Pierre Cazals, Aymeric François, Loïc Henriet +9 more

The Maximum Independent Set (MIS) problem is a fundamental combinatorial optimization task that can be naturally mapped onto the Ising Hamiltonian of neutral atom quantum processors. Given its connection to NP-hard problems and real-world applications, there has been significant experimental interest in exploring quantum advantage for MIS. Pioneering experiments on King's Lattice graphs suggested a quadratic speed-up over simulated annealing, but recent benchmarks using state-of-the-art methods found no clear advantage, likely due to the structured nature of the tested instances. In this work, we generate hard instances of unit-disk graphs by leveraging complexity theory results and varying key hardness parameters such as density and treewidth. For a fixed graph size, we show that increasing these parameters can lead to prohibitive classical runtime increases of several orders of magnitude. We then compare classical and quantum approaches on small instances and find that, at this scale, quantum solutions are slower than classical ones for finding exact solutions. Based on extended classical benchmarks at larger problem sizes, we estimate that scaling up to a thousand atoms with a 1 kHz repetition rate is a necessary step toward demonstrating a computational advantage with quantum methods.

arXiv:2502.04291•Physical Review Applied•Jan 29, 2026•27 citations
Quadratic Unconstrained Binary Optimization (QUBO) is a combinatorial optimization problem defined by an energy function that consists of a quadratic formula involving multiple binary variables.The goal of the QUBO problem is to find an optimal assignment of values to the variables that minimizes the energy function.With the increasing applicability of QUBO problems, QUBO solvers on different computing platforms have been developed.It is necessary to generate hard QUBO instances for improving and evaluating the performance of QUBO solvers.In this dissertation, we research in generating hard QUBO instances.First, we propose an effective method called bit duplication technique for generating hard QUBO instances with adjustable sizes.The idea is to duplicate specified number of 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 (n + m) bits (0 < m ≤ n).Second, in order to avoid the increase in the original size after performing bit duplication technique, we propose a novel technique which we call bit reduction to reduce the size of the original QUBO problem before preforming bit duplication technique.Through this method, hard QUBO instances can be generated without increasing the size of the original QUBO problem.By combining the bit duplication and bit reduction technique, we propose the method for generating hard instance of QUBO problems from any original QUBO problem without changing the size. 1 We use random QUBO problems, N-Queens problems, Traveling Salesman Problem (TSP), maximum weight matching (MWM) problems and Satisfiability problems (SAT) as original QUBO problems to generate hard QUBO instances.The performance of QUBO solvers including Gurobi optimizer, Fixstars Amplify AE, OpenJij with SA, D-Wave Hybrid and ABS2 QUBO solvers are evaluated for solving the generated hard QUBO instances.The experimental results show that generated QUBO instances are much hard for solving.
An algorithm for a particular problem may find some instances of the problem easier and others harder to solve, even for a fixed input size. We numerically analyze the relative hardness of MAX 2-SAT problem instances for various continuous-time quantum algorithms and a comparable classical algorithm. This has two motivations: To investigate whether small-sized problem instances, which are commonly used in numerical simulations of quantum algorithms for benchmarking purposes, are a good representation of larger instances in terms of their hardness to solve, and to determine the applicability of continuous-time quantum algorithms in a portfolio approach, where we take advantage of the variation in the hardness of instances between different algorithms by running them in parallel. We find that, while there are correlations in instance hardness between all of the algorithms considered, they appear weak enough that a portfolio approach would likely be desirable in practice. Our results also show a widening range of hardness of randomly generated instances as the problem size is increased, which demonstrates both the difference in the distribution of hardness at small sizes and the value of a portfolio approach that can reduce the number of extremely hard instances. We identify specific weaknesses of these quantum algorithms that can be overcome with a portfolio approach, such their inability to efficiently solve satisfiable instances (which is easy classically).
The Maximum Independent Set (MIS) problem is a fundamental combinatorial optimization task that can be naturally mapped onto the Ising Hamiltonian of neutral atom quantum processors. Given its connection to NP-hard problems and real-world applications, there has been significant experimental interest in exploring quantum advantage for MIS. Pioneering experiments on King's Lattice graphs suggested a quadratic speed-up over simulated annealing, but recent benchmarks using state-of-the-art methods found no clear advantage, likely due to the structured nature of the tested instances. In this work, we generate hard instances of unit-disk graphs by leveraging complexity theory results and varying key hardness parameters such as density and treewidth. For a fixed graph size, we show that increasing these parameters can lead to prohibitive classical runtime increases of several orders of magnitude. We then compare classical and quantum approaches on small instances and find that, at this scale, quantum solutions are slower than classical ones for finding exact solutions. Based on extended classical benchmarks at larger problem sizes, we estimate that scaling up to a thousand atoms with a 1 kHz repetition rate is a necessary step toward demonstrating a computational advantage with quantum methods.