tnac4o

The main module of the package. It puts together the heuristics to solve Ising-type optimization problems defined on a quasi-2d lattice (e.g., a chimera graph), or a Random Markov Field on 2d rectangular lattice.

tnac4o.tnac4o.load(file_name)[source]

Load solution of an instance from a file.

Parameters:file_name (str) – a path to file generated with method tnac4o.save().
Returns:instance of tnac4o class. Couplings are not loaded – they are not saved in the first place.
class tnac4o.tnac4o.tnac4o(mode='Ising', Nx=4, Ny=4, Nc=8, beta=1, J=None)[source]

Bases: object

Main class which collects all the methods to solve a given instance and store the results.

Parameters:
  • mode (str) –

    'Ising' assumes Ising-type representation of the problem with the cost function \(E(s) = \sum_{i<j} J_{ij} s_i s_j + \sum_i J_{ii} s_i\). The couplings \(J_{ij}\) form a 2d rectangular \(N_x \times N_y\) lattice of elementary cells with \(N_c\) spins in each cell. Allowed interactions include any couplings within block and couplings between spins in nearest-neighbor blocks.

    Spin index \(i = k N_x N_c+l N_c+m\), with \(k=0,1,\ldots,N_y-1\), \(l=0,1,\ldots,N_x-1\), \(m=0,1,\ldots,N_c-1\) (zero-based indexing is used). PEPS tensor corresponding to a given block is generated explicitly; hence \(N_c\) cannot be too large. The exact value depends on \(N_c\) itself, as well as the number of spins which interact with neighbouring blocks.

    Spins which are not active (with all \(J_{ij}\) equal 0), are automatically recognized. They are not taken into account during the search.

    'RMF' assumes a Random Markov Field type model on a 2d rectangular \(N_y \times N_x\) lattice with cost function \(E = \sum_{\langle i,j \rangle} E(s_i, s_j) + \sum_i E(s_i)\) and nearest-neighbour interactions only.

  • Nx, Ny, Nc (ints) – lattice shape.
  • beta (float) – sets the inverse temperature used during the search. It is the most relevant parameter: larger beta allows to better zoom in on low energy states, but makes tensor network contraction numerically less stable. Optimal beta might be instance dependent and for different classes of instances it should be found experimentaly.
  • J (others) – couplings. For mode 'Ising', it should be a list of \([i, j, J_{ij}]\). For mode 'RMF', it should be a dictionary with fields: ‘fun’ (a dictionary of possible matrices \(E(s_i, s_j)\) and \(E(s_i)\) ), ‘fac’ (a dictionary with indices (n1y,n1x,n2y,n2x) or (ny,nx) matching the interacting nearest-neighbour lattice sites with respective elements of ‘fun’. ‘N’ is an \(N_y \times N_x\) nparray of int with variable ranges.

Examples

ins = tnac4o.tnac4o(mode=’Ising’, Nx=16, Ny=16, Nc=8, beta=beta, J=J) initialises a model which includes interactions of a chimera graph C16 with 2048 spins (see e.g., https://docs.dwavesys.com/docs/latest/c_gs_4.html)

Returns:

Obtained results are stored as instance attributes (see below).
Variables:
  • energy – energy(-ies) of states obtained from searching or sampling.
  • probability – log2 of probability of the most probable state obtained during the search.
  • degeneracy – degeneracy of the ground state.
  • states – states of blocks from searching or sampling. In the mode 'Ising' use method binary_states() to get the bit strings.
  • discarded_probability – log2 of the largest probability discarded during the search.
  • negative_probability – a potential red flag. Takes values in [-1,0]. A negative value means that some conditional probabilities calculated from tensor network contraction were negative. This indicates that the contraction was not fully numerically stable. The value shows the ratio of negative and positive conditional probabilities for one block and partial configuration. The worst case is shown.
  • logger – logger
  • excitations_encoding – if the low-energy spectrum was searched,
  • is the index of the merging strategy, which was used. (this) –
  • el – tree representing the hierarchy of droplets, as obtained during merging.
  • d – dictionary of droplets’ shapes.
add_noise(amplitude=1e-07)[source]

Adds a small random noise to the couplings stored in the class.

It should be used to remove accidental degeneracies while searching for low-energy configurations using ‘excitations_encoding’ 2 or 3.

Parameters:amplitude (float) – the amplitude of the random noise.
binary_states(number=-1)[source]

Returns states in binary form.

1 - spin up \((s_i=+1)\); 0 - spin down \((s_i=-1)\); 2 - inactive spin

Parameters:number (int) – Maximal number of states to be returned. -1 returns all states.
Returns:nparray
decode_low_energy_states(max_dEng=0.0, max_states=1024)[source]

Decode found structure of excitations into the actuall low-energy states.

It can be used after method search_low_energy_spectrum().

Parameters:
  • max_dEng (float) – bound on excitation energy.
  • max_states (int) – bound on a number of generated states. States with smallest energies are selected.
exc_print()[source]

Display the excitations’ structure tree.

gibbs_sampling(M=1024, graduate_truncation=True, Dmax=32, tolS=1e-15, tolV=1e-10, max_sweeps=20)[source]

Sample from the Boltzman distribution on a quasi-2d graph.

Probabilities are kept as log2. Results are stored as instance attributes.

Parameters:
  • M (int) – number of configurations.
  • graduate_truncation (boolen) – more gradually truncates boundary MPS. Might be more precise, but slower.
  • Dmax (int) – maximal bond dimensions used in boundary MPS.
  • tolS (float) – truncate smaller singular values during svd in boundary MPS.
  • tolV (float) – condition for overlap convergence during one sweep in boundary MPS.
  • max_sweeps (int) – maximal number of sweeps of variational compression.
Returns:

Sampled energies.
precondition(mode='balancing', steps=2, beta_cond=[], Dmax_cond=[], max_scale=1024, graduate_truncation=False, tolS=1e-16, tolV=1e-10, max_sweeps=20)[source]

Apply the preconditioning procedure.

Parameters:
  • mode (str) – Type of heuristics used. For now, only ‘balancing’ trick is implemented.
  • steps (int) – number of default smaller betas used (if they are not provided explicitly, in which case betas are decreasing by a factor of two from the target one, with bond dimension set to 8).
  • beta_cond (list of floats) – beta’s used to search for preconditioning.
  • Dmax_cond (list of ints) – corresponding maximal bond dimensions used in boundary MPS.
  • max_scale (float) – bound on local rescaling used in one step.
  • tolS (float) – truncate smaller singular values during svd in boundary MPS.
  • tolV (float) – condition for overlap convergence during one sweep in boundary MPS.
  • graduate_truncation (boolen) – more gradually truncates boundary MPS. Might be more precise, but slower.
  • max_sweeps (int) – maximal number of sweeps of variational compression.
rotate_graph(rot=1)[source]

Rotate 2d graph by 90 degrees.

It is used to contract peps and perform search starting from different sited of the lattice. Rotations are cumulative.

save(file_name)[source]

Save solution of the instance to a .npy file.

Parameters:file_name (str) – where to save
search_ground_state(M=1024, relative_P_cutoff=1e-06, min_dEng=1e-12, graduate_truncation=True, Dmax=32, tolS=1e-16, tolV=1e-10, max_sweeps=20)[source]

Searches for the most probable state (ground state) on a quasi-2d graph.

Merge matching configurations during branch-and-bound search going line by line (\(n_y=0:N_y-1\)). It keeps track of GS degeneracy, distinguishing different energies with precision min_dEng. Probabilities are kept as log2. Results are stored as instance attributes.

Parameters:
  • M (int) – maximal number of branches (partial configurations) that are kept during the search.
  • relative_P_cutoff (float) – discard branches with a probability smaller by that factor comparing with most probable one.
  • min_dEng (float) – precision below which two states (perhaps partial) are considered to have the same energy.
  • graduate_truncation (boolen) – more gradually truncates boundary MPS. Might be more precise, but slower.
  • Dmax (int) – maximal bond dimensions used in boundary MPS.
  • tolS (float) – truncate smaller singular values during svd in boundary MPS.
  • tolV (float) – condition for overlap convergence during one sweep in boundary MPS.
  • max_sweeps (int) – maximal number of sweeps of variational compression.
Returns:

The lowest energy found.
search_low_energy_spectrum(excitations_encoding=1, M=1024, relative_P_cutoff=1e-06, max_dEng=0.0, lim_hd=0, min_dEng=1e-12, graduate_truncation=True, Dmax=32, tolS=1e-16, tolV=1e-10, max_sweeps=20)[source]

Searches for low-energy spectrum on a quasi-2d graph.

Merge matching configurations during branch-and-bound search going line by line (\(n_y=0:N_y-1\)). Information about excited states (droplets) is collected during merging, which allows reconstructing the low-energy spectrum. It keeps track of GS degeneracy, distinguishing different energies with precision min_dEng. Probabilities are kept as log2. Results are stored as instance attributes.

Parameters:
  • excitations_encoding (int) –

    Approach used to define independent/elementary droplets

    1 Independence determined based on the order of snake spanning 2d lattice line by line. It gives a one-to-one correspondence between the low-energy spectrum and the stored excitation structure (assuming, that the search itself was successful).

    2 Independent and elementary droplets determined based on adjacency matrix (i.e., graph of interactions). Droplets which are not single-connected are discarded during merging, leaving only the elementary, single-connected ones. A one-to-one correspondence between the low-energy spectrum and the stored excitation structure might be lost when merging configurations with many layers of the excitation hierarchy.

    3 As in 2 but excitations are compressed to one layer of hierarchy. It is useful only for problems with a single basin of attraction and low-energy excitations of small sizes but retains a one-to-one correspondence between the low-energy spectrum and the stored excitation structure.

  • M (int) – maximal number of branches (partial configurations) that are kept during the search.
  • relative_P_cutoff (float) – discard branches with a probability smaller by that factor comparing with most probable one.
  • max_dEng (float) – maximal excitation energy being targeted.
  • lim_hd (int) – Lower limit of Hamming distance between states (while merging). Outputs fewer states.
  • min_dEng (float) – precision below which two states (perhaps partial) are considered to have the same energy.
  • graduate_truncation (boolen) – more gradually truncates boundary MPS. Might be more precise, but slower.
  • Dmax (int) – maximal bond dimensions used in boundary MPS.
  • tolS (float) – truncate smaller singular values during svd in boundary MPS.
  • tolV (float) – condition for overlap convergence during one sweep in boundary MPS.
  • max_sweeps (int) – maximal number of sweeps of variational compression.
Returns:

The lowest energy found.
show_properties()[source]

Display basic properties of the lattice.

show_solution(state=False)[source]

Shows found solution and some info from search and contraction.