We show a similarity between two different classical simulation methods for measurement based quantum computation -- one relying on a low entanglement (tree tensor network) representation of the computer's state, and the other a tensor contraction method based on the topology of the graph state. We use this similarity to show that any quantum circuit that can be efficiently simulated via tensor contraction cannot produce much entanglement.
We show a similarity between two different classical simulation methods for measurement based quantum computation -- one relying on a low entanglement (tree tensor network) representation of the computer's state, and the other a tensor contraction method based on the topology of the graph state. We use this similarity to show that any quantum circuit that can be efficiently simulated via tensor contraction cannot produce much entanglement.
Tensor network theory and quantum simulation are, respectively, the key classical and quantum computing methods in understanding quantum many-body physics. Here, we introduce the framework of hybrid tensor networks with building blocks consisting of measurable quantum states and classically contractable tensors, inheriting both their distinct features in efficient representation of many-body wave functions. With the example of hybrid tree tensor networks, we demonstrate efficient quantum simulation using a quantum computer whose size is significantly smaller than the one of the target system. We numerically benchmark our method for finding the ground state of 1D and 2D spin systems of up to 8×8 and 9×8 qubits with operations only acting on 8+1 and 9+1 qubits, respectively. Our approach sheds light on simulation of large practical problems with intermediate-scale quantum computers, with potential applications in chemistry, quantum many-body physics, quantum field theory, and quantum gravity thought experiments.
We derive a rigorous upper bound on the classical computation time of finite-ranged tensor network contractions in d≥2 dimensions. Consequently, we show that quantum circuits of single-qubit and finite-ranged two-qubit gates can be classically simulated in subexponential time in the number of gates. Moreover, we present and implement an algorithm guaranteed to meet our bound and which finds contraction orders with vastly lower computational times in practice. In practically relevant cases this beats standard simulation schemes and, for certain quantum circuits, also a state-of-the-art method. Specifically, our algorithm leads to speedups of several orders of magnitude over naive contraction schemes for two-dimensional quantum circuits on as little as an 8×8 lattice. We obtain similarly efficient contraction schemes for Google's Sycamore-type quantum circuits, instantaneous quantum polynomial-time circuits, and nonhomogeneous (2+1)-dimensional random quantum circuits.
Classical simulation of quantum computation is necessary for studying the numerical behavior of quantum algorithms, as there does not yet exist a large viable quantum computer on which to perform numerical tests. Tensor network (TN) contraction is an algorithmic method that can efficiently simulate some quantum circuits, often greatly reducing the computational cost over methods that simulate the full Hilbert space. In this study we implement a tensor network contraction program for simulating quantum circuits using multi-core compute nodes. We show simulation results for the Max-Cut problem on 3- through 7-regular graphs using the quantum approximate optimization algorithm (QAOA), successfully simulating up to 100 qubits. We test two different methods for generating the ordering of tensor index contractions: one is based on the tree decomposition of the line graph, while the other generates ordering using a straight-forward stochastic scheme. Through studying instances of QAOA circuits, we show the expected result that as the treewidth of the quantum circuit's line graph decreases, TN contraction becomes significantly more efficient than simulating the whole Hilbert space. The results in this work suggest that tensor contraction methods are superior only when simulating Max-Cut/QAOA with graphs of regularities approximately five and below. Insight into this point of equal computational cost helps one determine which simulation method will be more efficient for a given quantum circuit. The stochastic contraction method outperforms the line graph based method only when the time to calculate a reasonable tree decomposition is prohibitively expensive. Finally, we release our software package, qTorch (Quantum TensOR Contraction Handler), intended for general quantum circuit simulation. For a nontrivial subset of these quantum circuits, 50 to 100 qubits can easily be simulated on a single compute node.
Various algorithms have been developed to simulate quantum circuits on classical hardware. Among the most prominent are approaches based on \emph{stabilizer decompositions} and \emph{tensor network contraction}. In this work, we present a unified framework that bridges these two approaches, placing them under a common formalism. Using this, we present two new algorithms to simulate an n-qubit circuit C: one that runs in O~(Ttw(C)) time and the other in O~(Tγ⋅tw(C)) time, where tw(C) and rw(C) refer to the the tree-width and rank-width, respectively, of a tensor network associated to C, T is the number of non-Clifford gates in C, and γ≈3.42. The proposed algorithms are simple, only require a linear amount of memory, are trivially parallelizable, and interact nicely with ZX-diagram simplification routines. Furthermore, we introduce the refined complexity measures \emph{focused tree-width} and \emph{focused rank-width}, which are always at least as efficient as their standard equivalent; these can be directly applied within our simulation algorithms, allowing for a more precise upper bound on the run time.
One of the key problems in tensor network based quantum circuit simulation is the construction of a contraction tree which minimizes the cost of the simulation, where the cost can be expressed in the number of operations as a proxy for the simulation running time. This same problem arises in a variety of application areas, such as combinatorial scientific computing, marginalization in probabilistic graphical models, and solving constraint satisfaction problems. In this paper, we reduce the computationally hard portion of this problem to one of graph linear ordering, and demonstrate how existing approaches in this area can be utilized to achieve results up to several orders of magnitude better than existing state of the art methods for the same running time. To do so, we introduce a novel polynomial time algorithm for constructing an optimal contraction tree from a given order. Furthermore, we introduce a fast and high quality linear ordering solver, and demonstrate its applicability as a heuristic for providing orderings for contraction trees. Finally, we compare our solver with competing methods for constructing contraction trees in quantum circuit simulation on a collection of randomly generated Quantum Approximate Optimization Algorithm Max Cut circuits and show that our method achieves superior results on a majority of tested quantum circuits. Reproducibility: Our source code and data are available at https://github.com/cameton/HPEC2022_ContractionTrees.
The treewidth of a graph is a useful combinatorial measure of how close the graph is to a tree. We prove that a quantum circuit with T gates whose underlying graph has a treewidth d can be simulated deterministically in TO(1)exp[O(d)] time, which, in particular, is polynomial in T if d=O(logT). Among many implications, we show efficient simulations for log-depth circuits whose gates apply to nearby qubits only, a natural constraint satisfied by most physical implementations. We also show that one-way quantum computation of Raussendorf and Briegel (Phys. Rev. Lett., 86 (2001), pp. 5188–5191), a universal quantum computation scheme with promising physical implementations, can be efficiently simulated by a randomized algorithm if its quantum resource is derived from a small-treewidth graph with a constant maximum degree. (The requirement on the maximum degree was removed in [I. L. Markov and Y. Shi, preprint:quant-ph/0511069].)