Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOptimization of CNOT circuits under topological constraints
283
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
Due to the decoherence of the state-of-the-art physical implementations of quantum computers, it is essential to parallelize the quantum circuits to reduce their depth. Two decades ago, Moore et al. demonstrated that additional qubits (or ancillae) could be used to design shallow parallel circuits for quantum operators. They proved that any $n$-qubit CNOT circuit could be parallelized to $O(log n)$ depth, with $O(n^2)$ ancillae. However, the near-term quantum technologies can only support limited amount of qubits, making space-depth trade-off a fundamental research subject for quantum-circuit synthesis. In this work, we establish an asymptotically optimal space-depth trade-off for the design of CNOT circuits. We prove that for any $mgeq0$, any $n$-qubit CNOT circuit can be parallelized to $Oleft(max left{log n, frac{n^{2}}{(n+m)log (n+m)}right} right)$ depth, with $O(m)$ ancillae. We show that this bound is tight by a counting argument, and further show that even with arbitrary two-qubit quantum gates to approximate CNOT circuits, the depth lower bound still meets our construction, illustrating the robustness of our result. Our work improves upon two previous results, one by Moore et al. for $O(log n)$-depth quantum synthesis, and one by Patel et al. for $m = 0$: for the former, we reduce the need of ancillae by a factor of $log^2 n$ by showing that $m=O(n^2/log^2 n)$ additional qubits suffice to build $O(log n)$-depth, $O(n^2/log n)$ size --- which is asymptotically optimal --- CNOT circuits; for the later, we reduce the depth by a factor of $n$ to the asymptotically optimal bound $O(n/log n)$. Our results can be directly extended to stabilizer circuits using an earlier result by Aaronson et al. In addition, we provide relevant hardness evidences for synthesis optimization of CNOT circuits in term of both size and depth.
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.
In this paper, we propose a novel quantum compiler optimization, named relaxed peephole optimization (RPO) for quantum computers. RPO leverages the single-qubit state information that can be determined statically by the compiler. We define that a qubit is in a basis state when, at a given point in time, its state is either in the X-, Y-, or Z-basis. When basis qubits are used as inputs to quantum gates, there exist opportunities for strength reduction, which replaces quantum operations with equivalent but less expensive ones. Compared to the existing peephole optimization for quantum programs, the difference is that our proposed optimization does not require an identical unitary matrix, thereby named `relaxed peephole optimization. We also extend our approach to optimize the quantum gates when some input qubits are in known pure states. Both optimizations, namely the Quantum Basis-state Optimization (QBO) and the Quantum Pure-state Optimization (QPO), are implemented in the IBMs Qiskit transpiler. Our experimental results show that our proposed optimization pass is fast and effective. The circuits optimized with our compiler optimizations obtain up to 18.0% (11.7% on average) fewer CNOT gates and up to 8.2% (7.1% on average) lower transpilation time than that of the most aggressive optimization level in the Qiskit compiler. When running on real quantum computers, the success rates of 3-qubit quantum phase estimation algorithm improve by 2.30X due to the reduced gate counts.
In this paper, we present approximation algorithms for combinatorial optimization problems under probabilistic constraints. Specifically, we focus on stochastic variants of two important combinatorial optimization problems: the k-center problem and the set cover problem, with uncertainty characterized by a probability distribution over set of points or elements to be covered. We consider these problems under adaptive and non-adaptive settings, and present efficient approximation algorithms for the case when underlying distribution is a product distribution. In contrast to the expected cost model prevalent in stochastic optimization literature, our problem definitions support restrictions on the probability distributions of the total costs, via incorporating constraints that bound the probability with which the incurred costs may exceed a given threshold.
This paper studies online optimization under inventory (budget) constraints. While online optimization is a well-studied topi
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
