Scientific Reports · 2022 · 17 citations · 33 references
ComputingComputer ScienceAlgorithmsOptimizationQuantum ComputingBoolean AlgebraBoolean Network ModelsBoolean OperationsQuantum AlgorithmsQuantum AnnealingQuantum ComputationBoolean Function DecompositionBoolean Matrix AlgebraNp-complete ProblemsNp-hardnessOptimization For High-dimensional DataQuantum Optimization AlgorithmsTensor DecompositionsTensor Factorization
Quantum annealers manufactured by D-Wave Systems, Inc., are computational devices capable of finding high-quality heuristic solutions of NP-hard problems. In this contribution, we explore the potential and effectiveness of such quantum annealers for computing Boolean tensor networks. Tensors offer a natural way to model high-dimensional data commonplace in many scientific fields, and representing a binary tensor as a Boolean tensor network is the task of expressing a tensor containing categorical (i.e., [Formula: see text]) values as a product of low dimensional binary tensors. A Boolean tensor network is computed by Boolean tensor decomposition, and it is usually not exact. The aim of such decomposition is to minimize the given distance measure between the high-dimensional input tensor and the product of lower-dimensional (usually three-dimensional) tensors and matrices representing the tensor network. In this paper, we introduce and analyze three general algorithms for Boolean tensor networks: Tucker, Tensor Train, and Hierarchical Tucker networks. The computation of a Boolean tensor network is reduced to a sequence of Boolean matrix factorizations, which we show can be expressed as a quadratic unconstrained binary optimization problem suitable for solving on a quantum annealer. By using a novel method we introduce called parallel quantum annealing, we demonstrate that Boolean tensor's with up to millions of elements can be decomposed efficiently using a DWave 2000Q quantum annealer.
33
Matplotlib: A 2D Graphics Environment
John D. Hunter · Computing in Science & Engineering · 2007 · 39.6K citations
Learning the parts of objects by non-negative matrix factorization
Daniel D. Lee, H. Sebastian Seung · Nature · 1999 · 14.1K citations
Tensor Decompositions and Applications
Tamara G. Kolda, Brett W. Bader · SIAM Review · 2009 · 10.5K citations
Some Mathematical Notes on Three-Mode Factor Analysis
Ledyard R Tucker · Psychometrika · 1966 · 4.3K citations