Papers for

optimization algorithm engineers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Efficient sampling algorithm for spin glass model below critical threshold

Sampling from the Sherrington-Kirkpatrick Model up to Criticality

Abstract: We prove that the simulated annealing algorithm efficiently samples from the Sherrington-Kirkpatrick model at inverse temperature $β< 1$ to an arbitrary inverse polynomial accuracy in total variation.

Tue 13 OctData Structures and Algorithms
The gist
There is a complex physical model called the Sherrington-Kirkpatrick model that helps scientists understand certain types of magnets and disorder. Sampling from this model means generating typical examples that follow the model’s random behavior. The authors show that a commonly used method, simulated annealing, can efficiently do this sampling when the temperature is above a certain level (below the critical inverse temperature value of 1). This means they can accurately generate examples from the model quickly under these conditions.
Open → 2610.17717v1

Quantum circuit built fast from weighted d-DNNF state descriptions

Quantum state preparation for weighted d-DNNF

Abstract: The quantum state preparation problem is to, given a description of a quantum state, efficiently generate a quantum circuit computing the state. We show that for quantum states described by weighted d-DNNF (deterministic, decomposable pseudo-Boolean circuits) a quantum circuit computing the state can be obtained in linear time up to complex arithmetic.

Thu 1 OctData Structures and Algorithms
The gist
Making a quantum computer perform a certain task often starts with preparing a specific quantum state. This paper shows that when a quantum state can be described using a special kind of mathematical structure called weighted d-DNNF, it’s possible to create the quantum instructions needed very quickly. The authors prove this process can be done in time proportional to the size of that description, making it more efficient than some previous methods. This helps simplify part of building quantum algorithms for states described this way.
Open → 2610.02094v1