pyQBTNs.src package

Submodules

pyQBTNs.src.Hierarchical_Tucker module

Hierarchical Tucker.

class pyQBTNs.src.Hierarchical_Tucker.Hierarchical_Tucker(**parameters)[source]

Bases: object

train(T, dimensions, ranks)[source]

Factor the input tensor using the Tucker_Recursive algorithm.

Parameters

T (numpy array) – Tensor to be factored.
dimensions (list) – tensor dimensions.
ranks (list) – factorization ranks.

Returns

HT – dictionary of the tensor.

Return type

dictionary

pyQBTNs.src.Matrix_Factorization module

Boolean Matrix Factorization.

class pyQBTNs.src.Matrix_Factorization.Matrix_Factorization(solver_method, NNSVD_INITIAL_STATE_FLAG=0, maximum_iterations=500, maximum_converged_iterations=100, number_of_random_initial_states=100, random_initial_state_lower_bound=0.01, random_initial_state_upper_bound=0.99, parallel_bool=False, random_state=42)[source]

Bases: object

Matrix Factorization

factor_matrix(X, RANK, A, B)[source]

Parameters

X (2-dimensional boolean numpy array) – Boolean matrix to be factored.
RANK (integer) – factorization rank.
A (2-dimensional boolean numpy array) – Initial state A.
B (2-dimensional boolean numpy array) – Initial state B.

Returns

A (2-dimensional boolean numpy array) – Best found factor (A) for X=AB.
B (2-dimensional boolean numpy array) – Best foudn factor (B) for X=AB.
bool – True if exact factorization was found. False otherwise
error_tracking (List) – List of hamming distances for each pair of factor matrices (A, B) found.
error_tracking_data (List) – Same as error_tracking, but also includes the pairs of matrices A and B.

train(X, RANK)[source]

Factor the input matrix into A and B given X in the problem X=AB.

Parameters

T (numpy array) – Tensor to be factored.
RANK (integer) – factorization rank.

Returns

A (numpy array) – First matrix factor.
B (numpy array) – Second matrix factor.

pyQBTNs.src.Tensor_Train_Iterative module

Tensor Train Iterative.

class pyQBTNs.src.Tensor_Train_Iterative.Tensor_Train_Iterative(**parameters)[source]

Bases: object

train(T, dimensions, ranks)[source]

Factor the input tensor using the Tensor_Train_Iterative algorithm.

Parameters

T (numpy array) – Tensor to be factored.
dimensions (list) – tensor dimensions.
ranks (list) – factorization ranks.

Returns

TTlist – List of factors.

Return type

list

pyQBTNs.src.Tensor_Train_Recursive module

Tensor Train Recursive.

class pyQBTNs.src.Tensor_Train_Recursive.Tensor_Train_Recursive(**parameters)[source]

Bases: object

train(T, dimensions, ranks)[source]

Factor the input tensor using the Tensor_Train_Recursive algorithm

Parameters

T (numpy array) – Tensor to be factored.
dimensions (list) – tensor dimensions.
ranks (list) – factorization ranks.

Returns

TTlist – List of factors.

Return type

list

pyQBTNs.src.Tucker_Iterative module

Tuckeer Iterative.

class pyQBTNs.src.Tucker_Iterative.Tucker_Iterative(**parameters)[source]

Bases: object

train(T, dimensions, ranks)[source]

Factor the input tensor using the Tucker_Iterative algorithm.

Parameters

T (numpy array) – Tensor to be factored.
dimensions (list) – tensor dimensions.
ranks (list) – factorization ranks.

Returns

T (numpy array) – tensor core.
matrixList (list) – list of matrices.

pyQBTNs.src.Tucker_Recursive module

Tucker Recursive.

class pyQBTNs.src.Tucker_Recursive.Tucker_Recursive(**parameters)[source]

Bases: object

train(T, dimensions, ranks)[source]

Factor the input tensor using the Tucker_Recursive algorithm

Parameters

T (numpy array) – Tensor to be factored.
dimensions (list) – tensor dimensions.
ranks (list) – factorization ranks.

Returns

core (numpy array) – tensor core.
factors (list) – list of matrix factors.

pyQBTNs.src.classical_solve module

Classical (local) solver methods.

pyQBTNs.src.classical_solve.batch_classical_single_QUBO(X, N, A, B, solver_method, random_state=42)[source]

Solves the individual column factorization problems using classical algorithms such as simulated anealing.

Parameters

X (2-d numpy array) – matrix to be factored.
N (int) – column index.
A (2-d numpy array) – Initial state.
B (2-d numpy array) – Initial state. Not used. Here for the logical consistency.
random_state (int, optional) – random state. The default is 42.

Returns

out – list of (b) columns which solve the matrix factorization problem of X=AB.

Return type

list

pyQBTNs.src.classical_solve.call_simulated_annealing(QUBO, random_state=42)[source]

Call the simulated annealing method from the DWave API

Parameters

QUBO (dictionary) – quadratic unconstrained binary optimization problem.
random_state (integer, optional) – random seed. The default is 42.

Returns

out_vector (list) – list of dictionaries, where each dictionary is a good solution to the QUBO.
CPU_TIME (float) – CPU process time.

pyQBTNs.src.classical_solve.call_steepest_descent(QUBO, random_state=42)[source]

Parameters

QUBO (dictionary) – quadratic unconstrained binary optimization problem.
random_state (TYPE, optional) – random seed. The default is 42.

Returns

out_vector (list) – list of dictionaries, where each dictionary is a good solution to the QUBO.
CPU_TIME (float) – CPU process time in seconds.

pyQBTNs.src.classical_solve.call_tabu_sampler(QUBO, random_state=42)[source]

Parameters

QUBO (dictionary) – quadratic unconstrained binary optimization problem.
random_state (integer, optional) – random seed. The default is 42.

Returns

out_vector (list) – list of dictionaries, where each dictionary is a good solution to the QUBO.
CPU_TIME (float) – CPU process time.

pyQBTNs.src.classical_solve.classical_single_QUBO(As, xs, all_QUBOS, solver_method, random_state=42)[source]

Uses classical QUBO solvers to solve individual QUBOs at a time

Parameters

As (dictionary) – In this case the dictionary has a single entry because we are only solving one QUBO at a time. The single value is a numpy array A from x=Ab (we are solving for the column vector b). The key is tracking which column-factorization sub-problem this A is from.
xs (dictionary) – In this case the dictionary has a single entry because we are only solving one QUBO at a time. The only value is a numpy array (vector) of x in x=Ab. The only key is tracking which column- factorization sub-problem this x is from.
all_QUBOS (dictionary) – In this case the dictionary has a single entry because we are only solving one QUBO at a time. The QUBO is the only value, and the key is the QUBO integer label from the embedding.
solver_method (string) – QUBO solver method. Allowed values are “classical-simulated-annealing”, “classical-steepest-descent”, “classsical-tabu-sampler”, “d-wave”
random_state (integer, optional) – random state seed. The default is 42.

Returns

bcol_solution_dict (dict) – Keys are the column-factorization sub problem index, and values are the solved b-column solutions.
TOTAL_CPU_TIME (float) – total CPU process time.

pyQBTNs.src.generate_fixed_embeddings module

pyQBTNs.src.generate_fixed_embeddings.iterative_embedding(CONNECTIVITY_GRAPH, target_clique_size, random_state=42)[source]

This heuristic method computes many disjoint embeddings for cliques of size target_clique_size onto CONNECTIVITY_GRAPH.

Parameters

CONNECTIVITY_GRAPH (networkx.Graph()) – Quantum annealer hardware connectivity graph.
target_clique_size (integer) – small clique we want to embed as many times as possible onto the hardware.
random_state (integer, optional) – random seed. The default is 42.

Returns

all_subgraphs – list of the edges of the subgraphs, each subgraph can embed a clique of size target_clique_size.

Return type

list

pyQBTNs.src.generate_fixed_embeddings.iterative_search(CONNECTIVITY_GRAPH, starting_node, target_clique_size, random_state=42)[source]

Parameters

CONNECTIVITY_GRAPH (networkx.Graph()) – quantum annealer hardware connectivity graph.
starting_node (integer) – integer that repressents a node in the hardware graph.
target_clique_size (integer) – small clique we want to embed multiple times.
random_state (integer, optional) – random seed. The default is 42.

Returns

-1 if search failed, otherwise a suitable subgraph for the small clique size.

Return type

-1 or netowkrx.Graph()

pyQBTNs.src.quantum_solve module

pyQBTNs.src.quantum_solve.batch_parallel_quantum_annealing(X, N, A, B, random_state=42)[source]

Submits multiple column factorizaiton problems at once to D-Wave (Up to however many small cliques were found in the embedding stage). This method is called parallel quantum annealing.

Parameters

X (2-d numpy array) – matrix to be factored.
N (int) – column index.
A (2-d numpy array) – Initial state.
B (2-d numpy array) – Initial state. Not used. Here for the logical consistency.
random_state (int, optional) – random state. The default is 42.

Returns

out – list of solved columns.

Return type

list

pyQBTNs.src.quantum_solve.batch_quantum_annealing(X, N, A, B, random_state=42)[source]

Submits one column factorization problem to D-Wave at a time; i.e. each column factorization problem is solved sequentially.

Parameters

X (2-d numpy array) – matrix to be factored.
N (int) – column index.
A (2-d numpy array) – Initial state.
B (2-d numpy array) – Initial state. Not used. Here for the logical consistency.
random_state (int, optional) – random state. The default is 42.

Returns

out – list of (b) columns.

Return type

list

pyQBTNs.src.quantum_solve.parallel_quantum_annealing(all_embs, As, xs, all_QUBOS, connectivity_graph, DWave_solver)[source]

Calls the DWave solver using the parallel quantum annealing method. Solving the boolean column factorization problem x=Ab, where x and b are columns and A is a matrix.

Parameters

all_embs (dict) – Parallel QA embeddings. Keys are unique embedding identifiers. Values are the small clique embeddings
As (dict) – Keys are problem indexes. Value is the initial state boolean array (matrix) A.
xs (dict) – Keys are problem indexes. Value is the x-column vector to be factored.
all_QUBOS (dict) – Keys are problem indexes. Values are QUBO dictionaries.
connectivity_graph (networkx.Graph()) – Undirected hardware connectivity graph of the DWave solver.
DWave_solver (dwave.cloud.client.solver) – DWave solver object.

Returns

resulting_columns – solved b-columns. Each key is the index for that column (so we can stitch together the results into our B matrix). Each value is a list of 0 and 1 (boolean) vectors.

Return type

dict

pyQBTNs.src.quantum_solve.quantum_annealing(As, xs, all_QUBOS, connectivity_graph, DWave_solver, complete_embedding)[source]

Non-Parallel Quantum Annealing For ranks that are not 3

Parameters

As (dict) – Keys are problem indexes. Value is the initial state boolean array (matrix) A.
xs (dict) – Keys are problem indexes. Value is the x-column vector to be factored.
all_QUBOS (dict) – Keys are problem indexes. Values are QUBO dictionaries.
connectivity_graph (networkx.Graph()) – Undirected hardware connectivity graph of the DWave solver.
DWave_solver (dwave.cloud.client.solver) – DWave solver object.
complete_embedding (dict) – Keys are the variable indexes (for the LANL 2000Q this is 0-64). Values are lists of the physical qubits (chain) for that variable index.

Returns

bcol_solution_dict – keys are the problem index. Values are the best found b-column for that particular column factorization problem.

Return type

dict

pyQBTNs.src.tensor_utils module

Tensor Utilities.

pyQBTNs.src.tensor_utils.boolArray(l, p)[source]

Generate random boolean array of size l with proportion of True/False according to p

Parameters

l (list) – list of sizes.
p (float) – proportion of False entries for constructing random boolean numpy arrays.

Returns

t – numpy array of order length of l.

Return type

numpy array

pyQBTNs.src.tensor_utils.construct_HT(dims, ranks, p)[source]

Construct HT dictionary

Parameters

dims (list) – list of dimensions.
ranks (list) – list of ranks.
p (float) – proportion of True and False elements for generating random boolean arrays.

Returns

HT – Reconstructed HT network.

Return type

dict

pyQBTNs.src.tensor_utils.construct_tensor_TT(dimensions, RANK, p)[source]

Constructs a tensor train tensor

Parameters

dimensions (list) – list of dimensions. The length of this list is the order.
RANK (int) – factorization rank.
p (float) – proportion of True and False elements for generating random boolean arrays.

Returns

reconstruct_TT(TT_list) – reconstructed Tensor Train tensor.

Return type

numpy array

pyQBTNs.src.tensor_utils.construct_tucker_tensor(dims, ranks, p, random_state=42)[source]

Parameters

dims (list) – list of dimensions.
ranks (list) – list of ranks.
p (float) – proportion of True and False elements for generating random boolean arrays.
random_state (int, optional) – random state. The default is 42.

Returns

core (numpy array) – DESCRIPTION.
factors (list) – List of numpy arrays, which are the constructed factors of the tensor
tensor (numpy array) – Tensor in the form of a boolean numpy array

pyQBTNs.src.tensor_utils.reconstruct_HT(HT)[source]

Reconstructs a tensor given an input of factors generated from running the Hierarchical Tucker algorithm.

Parameters: HT (dict) – factors from Hierarchical Tucker algorithm.
Returns: prod – tensor.
Return type: numpy array

pyQBTNs.src.tensor_utils.reconstruct_TT(factors)[source]

Reconstructs a tensor given an input of factors generated from running the Tensor Train algorithm.

Parameters: factors (list) – list of matrices.
Returns: prod – reconstructed tensor.
Return type: numpy array

pyQBTNs.src.tensor_utils.reconstruct_tucker(core, factors)[source]

Reconstructs a tensor given an input of factors generated from running the Tucker algorithm.

Parameters

core (numpy array) – core tensor.
factors (list) – list of matrices.

Returns

prod – tensor.

Return type

numpy array

pyQBTNs.src.tensor_utils.split_HT(dims, rng)[source]

Parameters

dims (list) – list of dimensions.
rng (range) – range of indexes in the dimension list.

Returns

dim (int) – product of dimensions in rng.
list – list of a subset (in rng) of dimensionss.

pyQBTNs.src.tensor_utils.split_TT(M, dims, ranks, rng)[source]

Parameters

M (numpy array) – Tensor or possible matrix. Boolean numpy array.
dims (list) – list of dimensions.
ranks (list) – list of ranks.
rng (range) – range of indexes in the dimension list.

Returns

dim (int) – product of dimensions in rng.
list – list of a subset (in rng) of dimensionss.
list – list of a subset (in rng) of ranks.

pyQBTNs.src.tensor_utils.split_tucker(dims, ranks, rng)[source]

Parameters

dims (list) – list of dimensions.
ranks (list) – list of ranks.
rng (range) – range of indexes in the dimension list.

Returns

dim (int) – product of dimensions in rng.
list – list of a subset (in rng) of dimensionss.
list – list of a subset (in rng) of ranks.

pyQBTNs.src.utils module

Utility methods.

pyQBTNs.src.utils.Start_DWave_connection()[source]

Creates a connection to a D-Wave quantum annealer using the defualt information in the user’s D-Wave config file.

Returns

connectivity_graph (networkx.Graph()) – Undirected hardware connectivity map of the quantum annealer.
DWave_solver (DWave solver object) – D-Wave solver object. You can pass problems to this object in order to submit them to be solved on the quantum annealer.
solver_name (str) – Name of the quantum annealer.

pyQBTNs.src.utils.column_solve_postprocess(b_cols, xcol, A)[source]

Solving x_col = A*b_col for b_col This method chooses the best b_col out of however many post-processed solutions were returned by the probabilistic sampler.

Parameters

b_cols (list) – List of b-column solutions found by the probabilistic sampler.
xcol (list) – target x-column we want to get the factorization of.
A (2-d Boolean numpy array (matrix)) – The A in x=Ab.

Returns

selection – b-column in the form of a list.

Return type

list

pyQBTNs.src.utils.combine_QUBO_storage(QUBO_storage, solved_QUBOs, column_solutions)[source]

Merges previous QUBO storage with new solutions.

Parameters

QUBO_storage (list) – Input QUBO storage list.
solved_QUBOs (dict) – The QUBOs that were solved in this latest iteration.
column_solutions (dict) – The associated b-column solutions for each of the solved QUBOs.

Returns

QUBO_storage – Updated QUBO storage with more QUBOs and their recorded solutions.

Return type

list

pyQBTNs.src.utils.delete_keys_from_dict(dictionary, keys_to_remove)[source]

Utility to remove specific keys from a dictionary.

Parameters

dictionary (dict) – Input dictionary.
keys_to_remove (list) – list of keys to remove from the dictionary. If this list is non-unique (i.e. has repeats), then there will be an error. Also, if any element in this list is not a key in the dictionary, there will be an error as well.

Returns

dictionary – Dictionary with keys removed.

Return type

dict

pyQBTNs.src.utils.filter_out_stored_QUBOs(QUBO_storage, all_QUBOS, all_xcols, all_Amatrices)[source]

Removes QUBOs which have been solved previously (as tracked by QUBO_storage). The best solutions that have been stored are then used instead of calling the solver again on the same QUBO.

Parameters

QUBO_storage (list) – Stored QUBOs (and their solutions) that have already been solved.
all_QUBOS (dict) – QUBOs to be (potentially) factored in this iteration.
all_xcols (dict) – The associated x-columns for each of these QUBOs to be solved.
all_Amatrices (dict) – The associated A matrices for each of these QUBOs to be solved..

Returns

storage_solutions (dict) – Any solved QUBOs that we do not need to solve again.
all_QUBOS (dict) – Updated QUBOs to solve.
all_xcols (dict) – Updated x-columns dictionary.
all_Amatrices (dict) – Updated A-columns dictionary.

pyQBTNs.src.utils.get_T_F_vecs(col)[source]

Input of a single column vector, returns the variable indices for both True and False values in the vector.

Parameters

col (list or numpy array) – Input column vector.

Returns

T (list) – Variable indicies for True variable state.
F (list) – Variable indicies for True variable state.

pyQBTNs.src.utils.get_bcols_from_samples(vectors, rank)[source]

From the solved vectors, compute the corresponding b-columns

Parameters

vectors (list) – post-processed vectors.
rank (int) – rank of the column factorization problem.

Returns

bcols – List of solutions found by the probabilistic sampler, in the form of b-columns.

Return type

list

pyQBTNs.src.utils.get_fixed_embedding(QUBO, complete_embedding, random_state=42)[source]

Given an input of a QUBO and an embedding, this function maps the variables from the qubo onto the embedding.

Parameters

QUBO (dict) – dictionary where the keys are linear or quadratic terms, and the values are real numbers. Represents a Quadratic Unconstrained Binary Optimization problem.
complete_embedding (dict) – all-to-all connectivity embedding for the given QUBO.
random_state (integer, optional) – random seed parameter. The default is 42.

Returns

QUBO_embedding – remapped embedding for QUBO.

Return type

dict

pyQBTNs.src.utils.get_hamming_distance(M1, M2)[source]

Gets the number of dis-similar entries betweeen two numpy arrays. Here the application is for boolean numpy array, whichis why this metric is actually hamming distance. Since this comparison is element-wise, the number of entries in each array needs to be equal.

Parameters

M1 (numpy.array) – Boolean numpy array of arbitrary dimensions. Could be a 1-d, 2-d array (matrix) or higher order (tensor).
M2 (numpy.array) – Boolean numpy array of arbitrary dimensions. Could be a 1-d, 2-d array (matrix) or higher order (tensor).

Returns

ham – Number of unequal elements between the two boolean numpy arrays.

Return type

int

pyQBTNs.src.utils.get_polynomial(A, V, indicator)[source]

returns Sympy polynomial. This polynmial is a HUBO (Higher order Unconstrained Binary Optimization) problem.

Parameters

A (Boolean numpy array) – matrix A in x=Ab.
V (list) – Vector passed from the method get_T_F_vecs().
indicator (bool) – Boolean variable for storing what coefficient we need in front of the polynomial A is the other factor of X (or approximate factor of X) we are using.

Returns

all_polynomials – Higher order polynomial.

Return type

Sympy polynomial

pyQBTNs.src.utils.get_qubo(col, A, bcol_len, random_state=42)[source]

Given an input of a column factorization problem, i.e. x=Ab where x and b are vectors and A is amtrix, we want to find b given x and A.

Parameters

col (list or numpy array) – x-column in the problem x=Ab.
A (Boolean numpy array) – matrix A in x=Ab.
bcol_len (int) – expected length of the b-column solution vector. Also equal to rank.
random_state (int, optional) – random state. The default is 42.

Returns

QUBO – QUBO created from the HUBO.

Return type

dict

pyQBTNs.src.utils.majority_vote(vectors, problem_embedding, random_state=42)[source]

Unembeds raw D-Wave samples using the majority vote function. Unbiased majority vote in that if the chain is split 50-50, then random choice is used.

Parameters

vectors (list) – Raw vectors from the D-Wave solver. The length is equal to the number of anneals. Each element in vectors is a list of length equal to the number of qubits on thee D-Wave device. For the case of a D-Wave 2000Q, the number of qubits is 2048 (including active and inactive).
problem_embedding (dict) – Logical embedding for the problem that D-Wave solved. Keys are variable names, and values are a list of physical qubits representing the logical state of the variable (key).

Returns

all_vectors_unembedded – List of dictionaries. The number of dictionaries is equal to the length of thee input variable vectors. Each dictionary is has the same keys as problem_embedding, and the values are either 0 1 since this function handles QUBOS.

Return type

list

pyQBTNs.src.utils.map_embedding_to_QUBO(QUBO, complete_embedding)[source]

For each variable in QUBO, this function maps that variable to a set of physical qubits found in complete_embedding.

Parameters

QUBO (dict) – keys are linear or quadratic terms, and values are the weights associated with each of those terms.
complete_embedding (dict) – Large all-to-all embedding for the quantum annealing hardware.

Returns

out – re-mapped embedding .

Return type

dict

pyQBTNs.src.utils.qubo(vars)[source]

expands out the polynomial so we can extract the coefficients for each variable

Parameters: vars (List) – List of sympy Symbols().
Returns: result – QUBO that has been expanded.
Return type: Sympy expression

pyQBTNs.src.utils.read_complete_embedding()[source]

reads in the all-to-all connectivity embedding that has been strored as a Json.

Returns: complete_embedding – Keys are logical variables numbereed 0-N. Values are lists of physical qubits that represent the logical state of the that variable (that variable being the key to that value).
Return type: dictionary

pyQBTNs.src.utils.read_rank3_parallel_QA_embeddings(random_state=42)[source]

Parameters: random_state (int, optional) – random seed. The default is 42.
Returns: rank_3_embeddings – List of disjoint clique-4 embeddings covering most of the quantum annealing hardware connectivity graph.
Return type: list

pyQBTNs.src.utils.remove_duplicate_QUBO(QUBO_storage)[source]

De-duplicates the QUBO storage list

Parameters: QUBO_storage (list) – List of QUBOs (each QUBO is a dictionary).
Returns: unique – de-duplicated list.
Return type: list

pyQBTNs.src.utils.remove_values_from_list(input_list, targ)[source]

Remove the value targ from the list

Parameters

input_list (list) – list to remove a value from.
targ (usually int, float or str) – target value to be removed.

Returns

List with the target value removed.

Return type

list

Module contents

© 2021. Triad National Security, LLC. All rights reserved. This program was produced under U.S. Government contract 89233218CNA000001 for Los Alamos National Laboratory (LANL), which is operated by Triad National Security, LLC for the U.S. Department of Energy/National Nuclear Security Administration. All rights in the program are reserved by Triad National Security, LLC, and the U.S. Department of Energy/National Nuclear Security Administration. The Government is granted for itself and others acting on its behalf a nonexclusive, paid-up, irrevocable worldwide license in this material to reproduce, prepare derivative works, distribute copies to the public, perform publicly and display publicly, and to permit others to do so.