Tensor networks gave rise to efficiently compact representations for certain classes of quantum states, and provide a graphical language to reason about quantum processes.
The methods reach outside of physics to large areas of computer science and even more recently have found applications in complex networks. In quantum physics, these methods are widely considered to form the backbone of tensor network contraction algorithms to model physical systems and are used in the abstract tensor languages to represent e.g. channels, maps, states and processes appearing in quantum theory. In particular, tensor networks provide a graphical language — the expressiveness of this language has fostered its growing popularity.
An early graphical rewrite by Roger Penrose tracing out half of an entangled Bell-state.
As a modeling language, tensor networks can be used to represent a wide class of physical and algorithmic scenarios, and our results have known to pinpoint the differences and similarities between these scenarios and have lead to even reveling differences in the associated diagrammatic language.
More specifically, our results in the areas of tensor network states includes the (i) development of the graphical tensor network language language resulting in the first connection between the computer science approach used in moiodal category theory and the tensor network states and matrix product states approach used in quantum theory (ii) the first merger of algebraic invariant theory with tensor network states which we then used to understand correlations in quantum systems and (iii) in developing new contraction algorithms for numerical computations –- both for problems faced in physics as well as counting problems in computer science.
Tensor Network Contractions for #SAT
Jacob Biamonte, Jacob Turner and Jason Morton
Journal of Statistical Physics 160, 1389 (2015)
[expand title=”abstract and link”]
The computational cost of counting the number of solutions satisfying a Boolean formula, which is a problem instance of #SAT, has proven subtle to quantify. Even when finding individual satisfying solutions is computationally easy (e.g. 2-SAT, which is in P), determining the number of solutions is #P-hard. Recently, computational methods simulating quantum systems experienced advancements due to the development of tensor network algorithms and associated quantum physics-inspired techniques. By these methods, we give an algorithm using an axiomatic tensor contraction language for n-variable #SAT instances with complexity $$O((g+cd)^{O(1)} 2^c)$$ where c is the number of COPY-tensors, g is the number of gates,
and d is the maximal degree of any COPY-tensor. Thus, counting problems can be solved efficiently when their tensor network expression has at most $$O(\log c)$$ COPY-tensors and polynomial fan-out. This framework also admits an intuitive proof of a variant of the Tovey conjecture (the r,1-SAT instance of the Dubois-Tovey theorem). This study increases the theory, expressiveness and application of tensor based algorithmic tools and provides an alternative insight on these problems which have a long history in statistical physics and computer science.arXiv:1405.7375 [quant-ph]
DOI: 10.1007/s10955-015-1276-z
[PDF]
[/expand]
Tensor Network Methods for Invariant Theory
Jacob Biamonte, Ville Bergholm, Marco Lanzagorta
J. Phys. A: Math. Theor. 46, 475301 (2013)
[expand title=”abstract and link”]
Invariant theory is concerned with functions that do not change under the action of a given group. Here we communicate an approach based on tensor networks to represent polynomial local unitary invariants of quantum states. This graphical approach provides an alternative to the polynomial equations that describe invariants, which often contain a large number of terms with coefficients raised to high powers. This approach also enables one to use known methods from tensor network theory (such as the matrix product state factorization) when studying polynomial invariants. As our main example, we consider invariants of matrix product states. We generate a family of tensor contractions resulting in a complete set of local unitary invariants that can be used to express the Renyi entropies. We find that the graphical approach to representing invariants can provide structural insight into the invariants being contracted, as well as an alternative, and sometimes much simpler, means to study polynomial invariants of quantum states. In addition, many tensor network methods, such as matrix product states, contain excellent tools that can be applied in the study of invariants.
[/expand]
Tensor Networks and Graphical Calculus for Open Quantum Systems
Chris Wood, Jacob Biamonte and David Cory
Quantum Information and Computation 15, 0579 (2015)
[expand title=”abstract and link”]
We describe a graphical calculus for completely positive maps and in doing so review the theory of open quantum systems and other fundamental primitives of quantum information theory using the language of tensor networks. In particular we demonstrate the construction of tensor networks to pictographically represent the Liouville-superoperator, Choi-matrix, process-matrix, Kraus, and system-environment representations for the evolution of quantum states, review how these representations interrelate, and illustrate how graphical manipulations of the tensor networks may be used to concisely transform between them. To further demonstrate the utility of the presented graphical calculus we include several examples where we provide arguably simpler graphical proofs of several useful quantities in quantum information theory including the composition and contraction of multipartite channels, a condition for whether an arbitrary bipartite state may be used for ancilla assisted process tomography, and the derivation of expressions for the average gate fidelity and entanglement fidelity of a channel in terms of each of the different representations of the channel.
[PDF]
[/expand]
Solving search problems by strongly simulating quantum circuits
T. H. Johnson, J. D. Biamonte, S. R. Clark, D. Jaksch
Scientific Reports 3, 1235 (2013)
[expand title=”abstract and link”]
Simulating quantum circuits using classical computers lets us analyse the inner workings of quantum algorithms. The most complete type of simulation, strong simulation, is believed to be generally inefficient. Nevertheless, several efficient strong simulation techniques are known for restricted families of quantum circuits and we develop an additional technique in this article. Further, we show that strong simulation algorithms perform another fundamental task: solving search problems. Efficient strong simulation techniques allow solutions to a class of search problems to be counted and found efficiently. This enhances the utility of strong simulation methods, known or yet to be discovered, and extends the class of search problems known to be efficiently simulable. Relating strong simulation to search problems also bounds the computational power of efficiently strongly simulable circuits; if they could solve all problems in P this would imply the collapse of the complexity hierarchy $$P \subseteq NP \subseteq # P$$.
DOI: 10.1038/srep01235
[PDF]
[/expand]
Tensor Networks for Entanglement Evolution
Sebastian Meznaric, Jacob Biamonte
Advances in Chemical Physics, Volume 154, Chapter 17, Pages 561-574 (2013)
Algebraically contractible topological tensor network states
S. J. Denny, J. D. Biamonte, D. Jaksch, S. R. Clark
J. Phys. A: Math. Theor. 45, 015309 (2012)
Undecidability in Tensor Network States
Jason Morton and Jacob Biamonte
Physical Review A Rapid Communications 86, 030301(R) (2012)
Ground State Spin Logic
J. D. Whitfield, M. Faccin, J. D. Biamonte
EPL 99, 57004 (2012)
Categorical Quantum Circuits
Ville Bergholm and J.D. Biamonte
Journal of Physics A: Mathematical and Theoretical 44:24, 245304 (2011)
Categorical Tensor Network States
J.D. Biamonte, Stephen R.Clark and Dieter Jaksch
AIP Advances 1:4, 042172 (2011)
[expand title=”abstract and link”]
We examine the use of string diagrams and the mathematics of category theory in the description of quantum states by tensor networks. This approach lead to a unification of several ideas, as well as several results and methods that have not previously appeared in either side of the literature. Our approach enabled the development of a tensor network framework allowing a solution to the quantum decomposition problem which has several appealing features. Specifically, given an n-body quantum state S, we present a new and general method to factor S into a tensor network of clearly defined building blocks. We use the solution to expose a previously unknown and large class of quantum states which we prove can be sampled efficiently and exactly. This general framework of categorical tensor network states, where a combination of generic and algebraically defined tensors appear, enhances the theory of tensor network states.
DOI: 10.1063/1.3672009
[PDF]
[/expand]
Version of map-state-duality using string diagrams [Adv. Chem. Phys. 154, 561 (2013)].
Tensor Networks in a Nutshell
talk given by Jacob Biamonte at the University of Latvia in Riga
[expand title=”abstract”]
Tensor networks are taking a central role in modern quantum physics and beyond. Their popularity in quantum physics stems from their ease of use as a graphical language to describe and pictorially reason about quantum circuits and protocols, renormalization, and numerical tensor contraction and simulation algorithms. The goal is to explain tensor networks as quickly and as painlessly as possible.
Beginning with the key definitions, the graphical tensor network language will be presented through example, including a few notational oddities that simply arise from linearity and the two-dimensional embedding. We will cover matrix product states (MPS), which gives an efficiently compact representation for certain classes of quantum states. We will also explain two tensor contractions that solve combinatorial counting problems. The first counts Boolean formulae solutions, whereas the second is Penrose’s tensor contraction algorithm, returning the number of edge coloring of 3-regular planar graphs. We will conclude by presenting a very brief survey of several current research directions.
[/expand]
Tensor Networks in a Nutshell