Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

International Conference on Natural Computation, Fuzzy Systems and Knowledge Discovery (ICNC-FSKD)

Dynamic contraction of tensor with quantum algorithm

Yinsheng Zhang, Hongjian Zhao, Fyodor O. Minakov

Published Jul 1, 2017• 0 citations
Publisher

Abstract

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.

DOI
10.1109/fskd.2017.8393303

Related papers

Approximate tensor network contraction

Alexander M. Dalzell, Sam McArdle, Mario Berta +10 more

This chapter covers the quantum algorithmic primitive of approximate tensor network contraction. Tensor networks are a powerful classical method for representing complex classical data as a network of individual tensor objects. To evaluate the tensor network, it must be contracted, which can be computationally challenging. A quantum algorithm for approximate tensor network contraction can provide a quantum speedup for contracting tensor networks that satisfy certain conditions.

Cambridge University Press eBooks•Apr 24, 2025•0 citations

Tensor quantum programming

A. Termanova, Artem A. Melnikov, Egor Mamenchikov +6 more

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.

arXiv:2403.13486•New Journal of Physics•Nov 28, 2024•21 citations

Recursive Multi-Tensor Contraction for XEB Verification of Quantum Circuits

Gleb Vyacheslavovich Kalachev, Pavel Panteleev, Man‐Hong Yung

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.

•Aug 12, 2021•4 citations

The Complexity of Contracting Planar Tensor Network

Ying Liu

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(d\sqrt{\max\{Δ,d\}N})$ size edge separator. Furthermore, we develop a $2^{O(d\sqrt{\max\{Δ,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 $2^{O(\sqrt{Δ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.

arXiv:2001.10204•Jan 28, 2020•2 citations

Exponential time complexity for contracting tensor networks

Ying Liu, Boning Meng, Juqiu Wang

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.

The Computer Journal•Jun 23, 2025•0 citations

A Parallel Tensor Network Contraction Algorithm and Its Applications in Quantum Computation

Fang Zhang

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.

•Jan 1, 2020•0 citations
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)O(d\sqrt{\max\{Δ,d\}N})O(dmax{Δ,d}N​) size edge separator. Furthermore, we develop a 2O(dmax⁡{Δ,d}N)2^{O(d\sqrt{\max\{Δ,d\}N})}2O(dmax{Δ,d}N​) time algorithm to contracting a tensor network consisting of NNN Boolean tensors, whose underlying graph is a finite element graph with maximum degree ΔΔΔ and has no face with more than ddd boundary edges in the planar skeleton, based on the 2O(ΔN)2^{O(\sqrt{ΔN})}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)O(k)O(k) size planar gadget for any Boolean symmetric tensor of dimension kkk, where the gadget only consists of Boolean tensors with dimension no more than 555. 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.
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 HHH-minor-free graphs (excluding any simple graph HHH 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.
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.