Search

Quasiprobabilistic cutting techniques allow us to partition large quantum circuits into smaller subcircuits by replacing non-local gates with probabilistic mixtures of local gates. The cost of this method is a sampling overhead that scales exponentially in the number of cuts. It is crucial to determine the minimal cost for gate cutting and to understand whether allowing for classical communication between subcircuits can improve the sampling overhead. In this work, we derive a closed formula for the optimal sampling overhead for cutting an arbitrary number of two-qubit unitaries and provide the corresponding decomposition. Interestingly, cutting several arbitrary two-qubit unitaries together is cheaper than cutting them individually and classical communication does not give any advantage. This is even the case when one cuts multiple non-local gates that are placed far apart in the circuit., Comment: 20 pages, 4 figures, added appendix A (circuit diagrams)

Decoding algorithms based on approximate tensor network contraction have proven tremendously successful in decoding 2D local quantum codes such as surface/toric codes and color codes, effectively achieving optimal decoding accuracy. In this work, we introduce several techniques to generalize tensor network decoding to higher dimensions so that it can be applied to 3D codes as well as 2D codes with noisy syndrome measurements (phenomenological noise or circuit-level noise). The three-dimensional case is significantly more challenging than 2D, as the involved approximate tensor contraction is dramatically less well-behaved than its 2D counterpart. Nonetheless, we numerically demonstrate that the decoding accuracy of our approach outperforms state-of-the-art decoders on the 3D surface code, both in the point and loop sectors, as well as for depolarizing noise. Our techniques could prove useful in near-term experimental demonstrations of quantum error correction, when decoding is to be performed offline and accuracy is of utmost importance. To this end, we show how tensor network decoding can be applied to circuit-level noise and demonstrate that it outperforms the matching decoder on the rotated surface code. Our code is available at https://github.com/ChriPiv/tndecoder3d, Comment: 21 pages, 10 figures. Code is available at https://github.com/ChriPiv/tndecoder3d

Circuit knitting is the process of partitioning large quantum circuits into smaller subcircuits such that the result of the original circuits can be deduced by only running the subcircuits. Such techniques will be crucial for near-term and early fault-tolerant quantum computers, as the limited number of qubits is likely to be a major bottleneck for demonstrating quantum advantage. One typically distinguishes between gate cuts and wire cuts when partitioning a circuit. The cost for any circuit knitting approach scales exponentially in the number of cuts. One possibility to realize a cut is via the quasiprobability simulation technique. In fact, we argue that all existing rigorous circuit knitting techniques can be understood in this framework. Furthermore, we characterize the optimal overhead for wire cuts where the subcircuits can exchange classical information or not. We show that the optimal cost for cutting $n$ wires without and with classical communication between the subcircuits scales as $O(16^n)$ and $O(4^n)$, respectively., Comment: 17 pages, 5 figures

The scarcity of qubits is a major obstacle to the practical usage of quantum computers in the near future. To circumvent this problem, various circuit knitting techniques have been developed to partition large quantum circuits into subcircuits that fit on smaller devices, at the cost of a simulation overhead. In this work, we study a particular method of circuit knitting based on quasiprobability simulation of nonlocal gates with operations that act locally on the subcircuits. We investigate whether classical communication between these local quantum computers can help. We provide a positive answer by showing that for circuits containing $n$ nonlocal CNOT gates connecting two circuit parts, the simulation overhead can be reduced from $O(9^n)$ to $O(4^n)$ if one allows for classical information exchange. Similar improvements can be obtained for general Clifford gates and, at least in a restricted form, for other gates such as controlled rotation gates., Comment: v3: 20 pages, 6 figures; published version

Recently, Renes proposed a quantum algorithm called belief propagation with quantum messages (BPQM) for decoding classical data encoded using a binary linear code with tree Tanner graph that is transmitted over a pure-state CQ channel [Renes, NJP 19 072001 (2017)]. The algorithm presents a genuine quantum counterpart to decoding based on the classical belief propagation algorithm, which has found wide success in classical coding theory when used in conjunction with LDPC or Turbo codes. More recently Rengaswamy et al. [npj Quantum Information 7 97 (2021)] observed that BPQM implements the optimal decoder on a small example code. Here we significantly expand the understanding, formalism, and applicability of the BPQM algorithm with the following contributions. First, we prove analytically that BPQM realizes optimal decoding for any binary linear code with tree Tanner graph. We also provide the first formal description of the BPQM algorithm in full detail and without any ambiguity. In so doing, we identify a key flaw overlooked in the original algorithm and subsequent works which implies quantum circuit realizations will be exponentially large in the code dimension. Although BPQM passes quantum messages, other information required by the algorithm is processed globally. We remedy this problem by formulating a truly message-passing algorithm which approximates BPQM and has quantum circuit complexity $\mathcal{O}(\text{poly } n, \text{polylog } \frac{1}{\epsilon})$, where $n$ is the code length and $\epsilon$ is the approximation error. Finally, we also propose a novel method for extending BPQM to factor graphs containing cycles by making use of approximate cloning. We show some promising numerical results that indicate that BPQM on factor graphs with cycles can significantly outperform the best possible classical decoder., Comment: 56 pages, 22 figures, submitted to Quantum

The Eastin-Knill theorem states that no quantum error correcting code can have a universal set of transversal gates. For CSS codes that can implement Clifford gates transversally it suffices to provide one additional non-Clifford gate, such as the T-gate, to achieve universality. Common methods to implement fault-tolerant T-gates like magic state distillation generate a significant hardware overhead that will likely prevent their practical usage in the near-term future. Recently methods have been developed to mitigate the effect of noise in shallow quantum circuits that are not protected by error correction. Error mitigation methods require no additional hardware resources but suffer from a bad asymptotic scaling and apply only to a restricted class of quantum algorithms. In this work, we combine both approaches and show how to implement encoded Clifford+T circuits where Clifford gates are protected from noise by error correction while errors introduced by noisy encoded T-gates are mitigated using the quasi-probability method. As a result, Clifford+T circuits with a number of T-gates inversely proportional to the physical noise rate can be implemented on small error-corrected devices without magic state distillation. We argue that such circuits can be out of reach for state-of-the-art classical simulation algorithms., Comment: v2: 11 pages, 7 figures; published version

Quantum error mitigation techniques can reduce noise on current quantum hardware without the need for fault-tolerant quantum error correction. For instance, the quasiprobability method simulates a noise-free quantum computer using a noisy one, with the caveat of only producing the correct expected values of observables. The cost of this error mitigation technique manifests as a sampling overhead which scales exponentially in the number of corrected gates. In this work, we present a new algorithm based on mathematical optimization that aims to choose the quasiprobability decomposition in a noise-aware manner. This directly leads to a significantly lower basis of the sampling overhead compared to existing approaches. A key element of the novel algorithm is a robust quasiprobability method that allows for a tradeoff between an approximation error and the sampling overhead via semidefinite programming., Comment: v2: 22 pages, 9 figures; published version

Deep neural networks (DNNs) have surpassed human-level accuracy in a variety of cognitive tasks but at the cost of significant memory/time requirements in DNN training. This limits their deployment in energy and memory limited applications that require real-time learning. Matrix-vector multiplications (MVM) and vector-vector outer product (VVOP) are the two most expensive operations associated with the training of DNNs. Strategies to improve the efficiency of MVM computation in hardware have been demonstrated with minimal impact on training accuracy. However, the VVOP computation remains a relatively less explored bottleneck even with the aforementioned strategies. Stochastic computing (SC) has been proposed to improve the efficiency of VVOP computation but on relatively shallow networks with bounded activation functions and floating-point (FP) scaling of activation gradients. In this paper, we propose ESSOP, an efficient and scalable stochastic outer product architecture based on the SC paradigm. We introduce efficient techniques to generalize SC for weight update computation in DNNs with the unbounded activation functions (e.g., ReLU), required by many state-of-the-art networks. Our architecture reduces the computational cost by re-using random numbers and replacing certain FP multiplication operations by bit shift scaling. We show that the ResNet-32 network with 33 convolution layers and a fully-connected layer can be trained with ESSOP on the CIFAR-10 dataset to achieve baseline comparable accuracy. Hardware design of ESSOP at 14nm technology node shows that, compared to a highly pipelined FP16 multiplier design, ESSOP is 82.2% and 93.7% better in energy and area efficiency respectively for outer product computation., Comment: 5 pages. 5 figures. Accepted at ISCAS 2020 for publication

Deep neural networks (DNNs) have revolutionized the field of artificial intelligence and have achieved unprecedented success in cognitive tasks such as image and speech recognition. Training of large DNNs, however, is computationally intensive and this has motivated the search for novel computing architectures targeting this application. A computational memory unit with nanoscale resistive memory devices organized in crossbar arrays could store the synaptic weights in their conductance states and perform the expensive weighted summations in place in a non-von Neumann manner. However, updating the conductance states in a reliable manner during the weight update process is a fundamental challenge that limits the training accuracy of such an implementation. Here, we propose a mixed-precision architecture that combines a computational memory unit performing the weighted summations and imprecise conductance updates with a digital processing unit that accumulates the weight updates in high precision. A combined hardware/software training experiment of a multilayer perceptron based on the proposed architecture using a phase-change memory (PCM) array achieves 97.73% test accuracy on the task of classifying handwritten digits (based on the MNIST dataset), within 0.6% of the software baseline. The architecture is further evaluated using accurate behavioral models of PCM on a wide class of networks, namely convolutional neural networks, long-short-term-memory networks, and generative-adversarial networks. Accuracies comparable to those of floating-point implementations are achieved without being constrained by the non-idealities associated with the PCM devices. A system-level study demonstrates 173x improvement in energy efficiency of the architecture when used for training a multilayer perceptron compared with a dedicated fully digital 32-bit implementation.

In-memory computing is a promising non-von Neumann approach for making energy-efficient deep learning inference hardware. Crossbar arrays of resistive memory devices can be used to encode the network weights and perform efficient analog matrix-vector multiplications without intermediate movements of data. However, due to device variability and noise, the network needs to be trained in a specific way so that transferring the digitally trained weights to the analog resistive memory devices will not result in significant loss of accuracy. Here, we introduce a methodology to train ResNet-type convolutional neural networks that results in no appreciable accuracy loss when transferring weights to in-memory computing hardware based on phase-change memory (PCM). We also propose a compensation technique that exploits the batch normalization parameters to improve the accuracy retention over time. We achieve a classification accuracy of 93.7% on the CIFAR-10 dataset and a top-1 accuracy on the ImageNet benchmark of 71.6% after mapping the trained weights to PCM. Our hardware results on CIFAR-10 with ResNet-32 demonstrate an accuracy above 93.5% retained over a one day period, where each of the 361,722 synaptic weights of the network is programmed on just two PCM devices organized in a differential configuration., Comment: This is a pre-print of an article accepted for publication in Nature Communications

We present a prediction of the Dirac semimetal (DSM) phase in MgTa2N3 based on first-principles calculations and symmetry analysis. In this material, the Fermi level is located exactly at the Dirac point without additional Fermi surface pockets. The band inversion associated with the Dirac cone involves the d orbitals of two structurally inequivalent Ta atoms with octahedral and trigonal prismatic coordination spheres. We further show that the lattice symmetry breaking can realize topological phase transitions from the DSM phase to a triple nodal point semimetal, Weyl semimetal or topological insulator. The topologically protected surface states and the non-protected Fermi arc surface states are also studied., Comment: 4 figures, 11 pages