Generating Hard Ising Instances With Planted Solutions Using Post-Quantum Cryptographic Protocols
arXiv:2308.09704 · doi:10.1016/j.future.2025.107721
Abstract
In this paper we present a novel method to generate hard instances with planted solutions based on the public-private McEliece post-quantum cryptographic protocol. Unlike other planting methods rooted in the infinite-size statistical analysis, our cryptographic protocol generates instances which are all hard (in cryptographic terms), with the hardness tuned by the size of the private key, and with a guaranteed unique ground state. More importantly, because of the private-public key protocol, planted solutions cannot be easily recovered by a direct inspection of the planted instances without the knowledge of the private key used to generate them, therefore making our protocol suitable to test and evaluate quantum devices without the risk of "backdoors" being exploited.
References in corpus (29)
- Supplementary information for "Quantum supremacy using a programmable superconducting processor"
- Physics-Inspired Optimization for Quadratic Unconstrained Problems Using a Digital Annealer
- Phase Transitions in the Coloring of Random Graphs
- Clustering of solutions in the random satisfiability problem
- Probing for quantum speedup in spin glass problems with planted solutions
- Universal Memcomputing Machines
- Hiding Quiet Solutions in Random Constraint Satisfaction Problems
- Strengths and weaknesses of weak-strong cluster problems: A detailed overview of state-of-the-art classical heuristics vs quantum approaches
- Phase transition in Random Circuit Sampling
- Efficient Cluster Algorithm for Spin Glasses in Any Space Dimension
- The Overlap Gap Property: a Geometric Barrier to Optimizing over Random Structures
- On the freezing of variables in random constraint satisfaction problems
- A deceptive step towards quantum speedup detection
- Constraint satisfaction problems with isolated solutions are hard
- Typology of phase transitions in Bayesian inference problems
- Quiet Planting in the Locked Constraint Satisfaction Problems
- From Near to Eternity: Spin-glass planting, tiling puzzles, and constraint satisfaction problems
- Practical engineering of hard spin-glass instances
- The Wishart planted ensemble: A tunably-rugged pairwise Ising model with a first-order phase transition
- The pitfalls of planar spin-glass benchmarks: Raising the bar for quantum annealers (again)
- Physics-Inspired Heuristics for Soft MIMO Detection in 5G New Radio and Beyond
- Limits and performances of algorithms based on simulated annealing in solving sparse hard inference problems
- Walksat stalls well below the satisfiability threshold
- Equation Planting: A Tool for Benchmarking Ising Machines
- Computational hardness of spin-glass problems with tile-planted solutions
- Patch-planting spin-glass solution for benchmarking
- Recovery thresholds in the sparse planted matching problem
- The planted -factor problem
- Quantum advantage for combinatorial optimization problems, Simplified