In the paper, contraction of a dynamic vector (i.e., both the number and the individuals of elements in the vector are non-deterministic) in a tensor is programmed. It accumulates complete N-combinations of one element of every M-set by recursion algorithm for object-oriented programming. Here, N is dynamic, i.e., uncertain before user's programming. This algorithm has overcome the difficulty of writing loop sentences in uncertain arity, yet the complexity of computation is exponential. So a quantum algorithm is proposed for realizing the computation in an acceptable time.
In the paper, contraction of a dynamic vector (i.e., both the number and the individuals of elements in the vector are non-deterministic) in a tensor is programmed. It accumulates complete N-combinations of one element of every M-set by recursion algorithm for object-oriented programming. Here, N is dynamic, i.e., uncertain before user's programming. This algorithm has overcome the difficulty of writing loop sentences in uncertain arity, yet the complexity of computation is exponential. So a quantum algorithm is proposed for realizing the computation in an acceptable time.
Abstract Running quantum algorithms often involves implementing complex quantum circuits with such a large number of multi-qubit gates that the challenge of tackling practical applications appears daunting. In this article, we propose a novel approach called Tensor Quantum Programming, which leverages tensor networks (TNs) for hybrid quantum computing. Our key insight is that the primary challenge of algorithms based on TNs lies in their high ranks (bond dimensions). Quantum computing offers a potential solution to this challenge, as an ideal quantum computer can represent tensors with arbitrarily high ranks in contrast to classical counterparts, which indicates the way towards quantum advantage. While tensor-based vector-encoding and state-readout are known procedures, the matrix-encoding required for performing matrix-vector multiplications directly on quantum devices is much less studied. We introduce an algorithm that encodes matrix product operators into quantum circuits with a depth that scales linearly with the number of qubits. We demonstrate the algorithm’s performance for matrices commonly encountered in differential equations, optimization problems, and quantum chemistry, for systems involving up to 50 qubits.
The computational advantage of noisy quantum computers have been demonstrated by sampling the bitstrings of quantum random circuits. An important issue is how the performance of quantum devices could be quantified in the so-called regime. The standard approach is through the linear cross entropy (XEB), where the theoretical value of the probability is required for each bitstring. However, the computational cost of XEB grows exponentially. So far, random circuits of the 53-qubit Sycamore chip was verified up to 10 cycles of gates only; the XEB fidelities of deeper circuits were approximated with simplified circuits instead. Here we present a multi-tensor contraction algorithm for speeding up the calculations of XEB of quantum circuits, where the computational cost can be significantly reduced through a recursive manner with some form of memoization. As a demonstration, we analyzed the experimental data of the 53-qubit Sycamore chip and obtained the exact values of the corresponding XEB fidelities up to 16 cycles using only moderate computing resources (few GPUs). If the algorithm was implemented on the Summit supercomputer, we estimate that for the 20-cycles supremacy circuits, it would only cost 7.5 days, which is several orders of magnitudes lower than previously estimated in the literature.
Tensor networks have been an important concept and technique in many research areas, such as quantum computation and machine learning. We study the exponential complexity of contracting tensor networks on two special graph structures: planar graphs and finite element graphs. We prove that any finite element graph has a O(dmax{Δ,d}N) size edge separator. Furthermore, we develop a 2O(dmax{Δ,d}N) time algorithm to contracting a tensor network consisting of N Boolean tensors, whose underlying graph is a finite element graph with maximum degree Δ and has no face with more than d boundary edges in the planar skeleton, based on the 2O(ΔN) time algorithm \cite{fastcounting} for planar Boolean tensor network contractions. We use two methods to accelerate the exponential algorithms by transferring high-dimensional tensors to low-dimensional tensors. We put up a O(k) size planar gadget for any Boolean symmetric tensor of dimension k, where the gadget only consists of Boolean tensors with dimension no more than 5. Another method is decomposing any tensor into a series of vectors (unary functions), according to its \emph{CP decomposition} \cite{tensor-rank}. We also prove the sub-exponential time lower bound for contracting tensor networks under the counting \emph{Exponential Time Hypothesis} (\#ETH) holds.
Tensors are a natural generalization of matrices, and tensor networks are a natural generalization of matrix products. Despite the simple definition of tensor networks, they are versatile enough to represent many different kinds of "products" that arise in various theoretical and practical problems. In particular, the powerful computational model of quantum computation can be defined almost entirely in terms of matrix products and tensor products, both of which are special cases of tensor networks. As such, (classical) algorithms for evaluating tensor networks have profound importance in the study of quantum computation. In this thesis, we design and implement a parallel algorithm for tensor network contraction. In addition to finding efficient contraction orders for a tensor network, we also dynamically slice it into multiple sub-tasks with lower space and time costs, in order to evaluate the tensor network in parallel. We refer to such an evaluation strategy as a contraction scheme for the tensor network. In addition, we introduce a local optimization procedure that improves the efficiency of the contraction schemes we find. We also investigate the applications of our parallel tensor network contraction algorithm in quantum computation. The most ready application is the simulation of random quantum supremacy circuits, where we benchmark our algorithm to demonstrate its advantage over other similar tensor network based simulators. Other applications we found include evaluating the energy function of a Quantum Approximate Optimization Algorithm (QAOA), and simulating surface codes under a realistic error model with crosstalk.
Abstract This article establishes a unified complexity framework for tensor network contraction—a fundamental counting problem. Since the computational complexity crucially depends on the underlying graph’s separator properties, we develop edge separator theorems for finite element graphs and H-minor-free graphs (excluding any simple graph H as a minor), and present sub-exponential contraction algorithms for these graph classes. These algorithms, along with the algorithm for contraction on planar graphs are further accelerated by transforming each high-dimensional tensor into a series of low-dimensional tensors. Two methods are involved in this process respectively—the “adder” gadget that can equivalently represent any Boolean symmetric tensor, and the CANDECOMP/PARAFAC decomposition that can express any tensor as vector product sums. In particular, we prove corresponding lower bounds under #ETH, establishing near-optimality of our algorithms. Also, we present a treewidth-parameterized contraction algorithm, and therefore develop a fine-grained dichotomy for tensor network contraction, contingent on the Hadwiger number.