### 1 unstable release

0.1.0 | Mar 23, 2024 |
---|

#**171** in Science

**GPL-3.0-only**

55KB

965 lines

# Ernst: 2D Spin Glass Simulation for quantum annealing

Quantum Annealing is an interesting way to leverage physical quantum effects to solve NP-hard problems. It relies on encoding problems as a single 2-dimensional Spin Glass, such that its degenerate ground states will map one-to-one to the solutions being sought.

The raison d'etre of this library is to make it easy for you to create spin glasses, simulate them, and then send them over to a quantum annealer.

## Functionality

With

you can:`Ernst`

- Incrementally build a 2D spin glass with the extensible

struct, alongside a library of pre-built logic gates`SpinNetwork` - Find its exact ground states with

(only recommended if the number of spins is < 48)`find_all_ground_states` - Efficiently seek for ground states (with history) of potentially very large spin networks with
`run_simulated_annealing` - Get the

and`h`

components of the`J`

hamiltonian to send to`SpinNetwork``D``-`wave

Here is an example:

`use` `ernst``::``spin_network``::`SpinNetwork`;`
`use` `ernst``::``types``::``{`ExternalMagneticField`,` Interactions`}``;`
`use` `std``::``time``::`Instant`;`
`use` `ernst``::``nodelib``::``logic_gates``::``OR``;`
`fn` `main``(``)`` ``{`
`let` some_h`:` ExternalMagneticField `=` `vec!``[`
`5.``0``,` `5.``0``,` `5.``0``,` `0.``0``,` `0.``0``,` `0.``0``,` `0.``0``,` `0.``5``,` `0.``5``,` `-``1.``0``,` `0.``5``,` `0.``5``,` `-``1.``0``,` `0.``5``,` `0.``5``,` `-``1.``0``,` `0.``5``,`
`0.``5``,` `-``1.``0``,`
`]``;`
`let` some_j`:` Interactions `=` `vec!``[`
`(``0``,` `7``,` `1.``0``)``,`
`(``1``,` `8``,` `1.``0``)``,`
`(``7``,` `8``,` `-``0.``5``)``,`
`(``7``,` `9``,` `1.``0``)``,`
`(``8``,` `9``,` `1.``0``)``,`
`(``1``,` `10``,` `1.``0``)``,`
`(``2``,` `11``,` `1.``0``)``,`
`(``10``,` `11``,` `-``0.``5``)``,`
`(``10``,` `12``,` `1.``0``)``,`
`(``11``,` `12``,` `1.``0``)``,`
`(``0``,` `13``,` `1.``0``)``,`
`(``4``,` `14``,` `1.``0``)``,`
`(``13``,` `14``,` `-``0.``5``)``,`
`(``13``,` `15``,` `1.``0``)``,`
`(``14``,` `15``,` `1.``0``)``,`
`(``3``,` `16``,` `1.``0``)``,`
`(``2``,` `17``,` `1.``0``)``,`
`(``16``,` `17``,` `-``0.``5``)``,`
`(``16``,` `18``,` `1.``0``)``,`
`(``17``,` `18``,` `1.``0``)``,`
`(``3``,` `9``,` `1.``0``)``,`
`(``4``,` `12``,` `1.``0``)``,`
`(``5``,` `15``,` `1.``0``)``,`
`(``6``,` `18``,` `1.``0``)``,`
`]``;`
`let` now `=` `Instant``::`now`(``)``;`
`let` exact_ground_states `=` `ernst``::``solvers``::`find_all_ground_states`(``&`some_j`,` `&`some_h`)``;`
`let` time_to_compute `=` now`.``elapsed``(``)``.``as_millis``(``)``;`
`println!``(``"`Complex spin glass ground state - took: `{}` ms`"``,` time_to_compute`)``;`
`for` ground_state `in` exact_ground_states `{`
`println!``(`
`"``\t`Energy: `{}` - State: `{:?}``"``,`
ground_state`.``0``,` ground_state`.``1`
`)``;`
`}`
`let` now `=` `Instant``::`now`(``)``;`
`let` approximate_ground_states `=` `ernst``::``solvers``::`simulated_annealing`(``&`some_j`,` `&`some_h`,` `None``)``;`
`let` time_to_compute `=` now`.``elapsed``(``)``.``as_millis``(``)``;`
`println!``(``"``\n`Complex spin glass ground state with simulated annealing - took: `{}` ms`"``,` time_to_compute`)``;`
`for` ground_state `in` approximate_ground_states `{`
`println!``(`
`"``\t`Energy: `{}` - State: `{:?}` - Found in sweep number: `{}``"``,`
ground_state`.``0``,` ground_state`.``1``,` ground_state`.``2`
`)``;`
`}`
`let` `mut` spin_network `=` `SpinNetwork``::`new`(``)``;`
`let` s0 `=` spin_network`.``add_input_node``(``0.``0``)``;`
`let` s1 `=` spin_network`.``add_input_node``(``0.``0``)``;`
`let` s2 `=` spin_network`.``add_input_node``(``0.``0``)``;`
`let` or_gate `=` `OR``::`default`(``)``;`
`let` z_aux `=` spin_network`.``add_binary_node``(`s0`,` s1`,` `&`or_gate`)``;`
`let` z `=` spin_network`.``add_binary_node``(`z_aux`,` s2`,` `&`or_gate`)``;`
`let` interesting_spins `=` `vec!``[`s0`,` s1`,` s2`,` z`]``;`
`let` ternary_or_ground_states `=` spin_network`.``find_all_ground_states``(``Some``(`interesting_spins`.``clone``(``)``)``)``;`
`println!``(``"``\n`Ternary OR spin glass ground states:`"``)``;`
`for` ground_state `in` ternary_or_ground_states `{`
`println!``(``"``\t`Energy: `{}` - State: `{:?}``"``,` ground_state`.``0``,` ground_state`.``1``)``;`
`}`
`let` copy_ground_states `=` spin_network`.``run_simulated_annealing``(``None``,` `Some``(`interesting_spins`)``)``;`
`println!``(``"``\n`Ternary OR spin glass ground states with simulated annealing:`"``)``;`
`for` ground_state `in` copy_ground_states `{`
`println!``(``"``\t`Energy: `{}` - State: `{:?}` - Found in sweep number: `{}``"``,` ground_state`.``0``,` ground_state`.``1``,` ground_state`.``2``)``;`
`}`
`}`

## Implementation

This library is optimized for incremental computation on a CPU. It does not make use of a linear algebra library. Its source of efficiency lies in cleverly doing incremental adjustments to the energy calculation with a Fenwick Tree.

## Why is it called Ernst?

The energy of a spin glass configuration is often computed according to the hamiltonian of a well-known statistical mechanics model, the Ising Model, which is named after Ernst Ising.

## Roadmap

- Parallel tempering
- Bayesian Optimisation

## Ernst for commercial projects

Are you interested in using Ernst for a commercial quantum optimization project? Then hit me up at @protonmail.ch

## Ernst for research

If you find this project useful for your research, you may cite it as follows:

`@misc{Rucy2024,
author = {Rucy, B.C.D.L}
title = {Ernst},
year = {2024},
publisher = {GitHub},
journal = {GitHub repository},
howpublished = {\url{https://github.com/brurucy/ernst}},
}
`

Additionally, you may consider adding a star to the repository. This positive feedback improves the visibility of the project.

#### Dependencies

~2.5MB

~40K SLoC