Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userReducing the CNOT count for Clifford+T circuits on NISQ architectures
77
0
0.0
(
0
)
Added by
Priyanka Mukhopadhyay Dr
Publication date
2020
fields
Physics
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
While mapping a quantum circuit to the physical layer one has to consider the numerous constraints imposed by the underlying hardware architecture. Connectivity of the physical qubits is one such constraint that restricts two-qubit operations such as CNOT to connected qubits. SWAP gates can be used to place the logical qubits on admissible physical qubits, but they entail a significant increase in CNOT-count, considering the fact that each SWAP gate can be implemented by 3 CNOT gates. In this paper we consider the problem of reducing the CNOT-count in Clifford+T circuits on connectivity constrained architectures such as noisy intermediate-scale quantum (NISQ) (Preskill, 2018) computing devices. We slice the circuit at the position of Hadamard gates and build the intermediate portions. We investigated two kinds of partitioning - (i) a simple method of partitioning the gates of the input circuit based on the locality of H gates and (ii) a second method of partitioning the phase polynomial of the input circuit. The intermediate {CNOT,T} sub-circuits are synthesized using Steiner trees, significantly improving on the methods introduced by Nash, Gheorghiu, Mosca[2020] and Kissinger, de Griend[2019]. We compared the performance of our algorithms while mapping different benchmark circuits as well as random circuits to some popular architectures such as 9-qubit square grid, 16-qubit square grid, Rigetti 16-qubit Aspen, 16-qubit IBM QX5 and 20-qubit IBM Tokyo. We found that for both the benchmark and random circuits our first algorithm that uses the simple slicing technique dramatically reduces the CNOT-count compared to naively using SWAP gates. Our second slice-and-build algorithm also performs very well for benchmark circuits.
rate research
Read More
In the era of noisy intermediate-scale quantum (NISQ), executing quantum algorithms on actual quantum devices faces unique challenges. One such challenge is that quantum devices in this era have restricted connectivity: quantum gates are allowed to act only on specific pairs of physical qubits. For this reason, a quantum circuit needs to go through a compiling process called qubit routing before it can be executed on a quantum computer. In this study, we propose a CNOT synthesis method called the token reduction method to solve this problem. The token reduction method works for all quantum computers whose architecture is represented by connected graphs. A major difference between our method and the existing ones is that our method synthesizes a circuit to an output qubit mapping that might be different from the input qubit mapping. The final mapping for the synthesis is determined dynamically during the synthesis process. Results showed that our algorithm consistently outperforms the best publicly accessible algorithm for all of the tested quantum architectures.
Currently available quantum computing hardware platforms have limited 2-qubit connectivity among their addressable qubits. In order to run a generic quantum algorithm on such a platform, one has to transform the initial logical quantum circuit describing the algorithm into an equivalent one that obeys the connectivity restrictions. In this work we construct a circuit synthesis scheme that takes as input the qubit connectivity graph and a quantum circuit over the gate set generated by ${text{CNOT},R_{Z}}$ and outputs a circuit that respects the connectivity of the device. As a concrete application, we apply our techniques to Googles Bristlecone 72-qubit quantum chip connectivity, IBMs Tokyo 20-qubit quantum chip connectivity, and Rigettis Acorn 19-qubit quantum chip connectivity. In addition, we also compare the performance of our scheme as a function of sparseness of randomly generated quantum circuits. Note: Recently, the authors of arXiv:1904.00633 independently presented a similar optimization scheme. Our work is independent of arXiv:1904.00633, being a longer version of the seminar presented by Beatrice Nash at the Dagstuhl Seminar 18381: Quantum Programming Languages, pg. 120, September 2018, Dagstuhl, Germany, slide deck available online at https://materials.dagstuhl.de/files/18/18381/18381.BeatriceNash.Slides.pdf.
We present a constructive method to create quantum circuits that implement oracles $|xrangle|yrangle|0rangle^k mapsto |xrangle|y oplus f(x)rangle|0rangle^k$ for $n$-variable Boolean functions $f$ with low $T$-count. In our method $f$ is given as a 2-regular Boolean logic network over the gate basis ${land, oplus, 1}$. Our construction leads to circuits with a $T$-count that is at most four times the number of AND nodes in the network. In addition, we propose a SAT-based method that allows us to trade qubits for $T$ gates, and explore the space/complexity trade-off of quantum circuits. Our constructive method suggests a new upper bound for the number of $T$ gates and ancilla qubits based on the multiplicative complexity $c_land(f)$ of the oracle function $f$, which is the minimum number of AND gates that is required to realize $f$ over the gate basis ${land, oplus, 1}$. There exists a quantum circuit computing $f$ with at most $4 c_land(f)$ $T$ gates using $k = c_land(f)$ ancillae. Results known for the multiplicative complexity of Boolean functions can be transferred. We verify our method by comparing it to different state-of-the-art compilers. Finally, we present our synthesis results for Boolean functions used in quantum cryptoanalysis.
CNOT circuit is the key gadget for entangling qubits in quantum computing systems. However, the qubit connectivity of noisy intermediate-scale quantum (NISQ) devices is constrained by their topological structures. To improve the performance of CNOT circuits on NISQ devices, we investigate the optimization of the size/depth of CNOT circuits under topological constraints. We firstly present a method that can optimize the size of any $n$-qubit CNOT circuit to less than $2n^2$ on any connected graph, which is optimal for sparsely connected structures. The simulation experiment shows that our method performs better than state-of-the-art results. Specifically, we present two detailed examples to illustrate the applicability of our algorithm. Furthermore, for the future device with a denser structure, we give a better optimization method that achieves $O(n^2/log delta)$ size on a graph with the minimum degree $delta$, which is optimal on the regular graph. Secondly, for the grid structure, which is commonly used in current quantum devices, we demonstrate that the depth of any $n$-qubit CNOT circuit can be optimized to be linear in $n$ with certain ancillary qubits (ancillas). Our experimental results indicate this method has significant improvements compared with all of the existing methods. We further implement the two circuits commonly used in quantum variational algorithms and quantum chemistry on the 5-qubit IBMQ devices by leverage of our optimization algorithm, the experimental results show the optimized circuit has far less error when there exists noise compared to IBM mapping method.
The multiplicative depth of a logic network over the gate basis ${land, oplus, eg}$ is the largest number of $land$ gates on any path from a primary input to a primary output in the network. We describe a dynamic programming based logic synthesis algorithm to reduce the multiplicative depth in logic networks. It makes use of cut enumeration, tree balancing, and exclusive sum-of-products (ESOP) representations. Our algorithm has applications to cryptography and quantum computing, as a reduction in the multiplicative depth directly translates to a lower $T$-depth of the corresponding quantum circuit. Our experimental results show improvements in $T$-depth over state-of-the-art methods and over several hand-optimized quantum circuits for instances of AES, SHA, and floating-point arithmetic.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
