Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOptimal Space-Depth Trade-Off of CNOT Circuits in Quantum Logic Synthesis
157
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
We show that the quantum parity gate on $n > 3$ qubits cannot be cleanly simulated by a quantum circuit with two layers of arbitrary C-SIGN gates of any arity and arbitrary 1-qubit unitary gates, regardless of the number of allowed ancilla qubits. This is the best known and first nontrivial separation between the parity gate and circuits of this form. The same bounds also apply to the quantum fanout gate. Our results are incomparable with those of Fang et al. [3], which apply to any constant depth but require a sublinear number of ancilla qubits on the simulating circuit.
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.
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.
We derive a state dependent error-disturbance trade-off based on a statistical distance in the sequential measurements of a pair of noncommutative observables and experimentally verify the relation with a photonic qubit system. We anticipate that this Letter may further stimulate the study on the quantum uncertainty principle and related applications in quantum measurements.
We present a synthesis framework to map logic networks into quantum circuits for quantum computing. The synthesis framework is based on LUT networks (lookup-table networks), which play a key role in conventional logic synthesis. Establishing a connection between LUTs in a LUT network and reversible single-target gates in a reversible network allows us to bridge conventional logic synthesis with logic synthesis for quantum computing, despite several fundamental differences. We call our synthesis framework LUT-based Hierarchical Reversible Logic Synthesis (LHRS). Input to LHRS is a classical logic network; output is a quantum network (realized in terms of Clifford+$T$ gates). The framework offers to trade-off the number of qubits for the number of quantum gates. In a first step, an initial network is derived that only consists of single-target gates and already completely determines the number of qubits in the final quantum network. Different methods are then used to map each single-target gate into Clifford+$T$ gates, while aiming at optimally using available resources. We demonstrate the effectiveness of our method in automatically synthesizing IEEE compliant floating point networks up to double precision. As many quantum algorithms target scientific simulation applications, they can make rich use of floating point arithmetic components. But due to the lack of quantum circuit descriptions for those components, it can be difficult to find a realistic cost estimation for the algorithms. Our synthesized benchmarks provide cost estimates that allow quantum algorithm designers to provide the first complete cost estimates for a host of quantum algorithms. Thus, the benchmarks and, more generally, the LHRS framework are an essential step towards the goal of understanding which quantum algorithms will be practical in the first generations of quantum computers.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
