Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userLowering the T-depth of Quantum Circuits By Reducing the Multiplicative Depth Of Logic Networks
148
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
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.
A scheme for measuring complex temperature partition functions of Ising models is introduced. In the context of ordered qubit registers this scheme finds a natural translation in terms of global operations, and single particle measurements on the edge of the array. Two applications of this scheme are presented. First, through appropriate Wick rotations, those amplitudes can be analytically continued to yield estimates for partition functions of Ising models. Bounds on the estimation error, valid with high confidence, are provided through a central-limit theorem, which validity extends beyond the present context. It holds for example for estimations of the Jones polynomial. Interestingly, the kind of state preparations and measurements involved in this application can in principle be made instantaneous, i.e. independent of the system size or the parameters being simulated. Second, the scheme allows to accurately estimate some non-trivial invariants of links. A third result concerns the computational power of estimations of partition functions for real temperature classical ferromagnetic Ising models on a square lattice. We provide conditions under which estimating such partition functions allows one to reconstruct scattering amplitudes of quantum circuits making the problem BQP-hard. Using this mapping, we show that fidelity overlaps for ground states of quantum Hamiltonians, which serve as a witness to quantum phase transitions, can be estimated from classical Ising model partition functions. Finally, we show that the ability to accurately measure corner magnetizations on thermal states of two-dimensional Ising models with magnetic field leads to fully polynomial random approximation schemes (FPRAS) for the partition function. Each of these results corresponds to a section of the text that can be essentially read independently.
Random quantum circuits have played a central role in establishing the computational advantages of near-term quantum computers over their conventional counterparts. Here, we use ensembles of low-depth random circuits with local connectivity in $Dge 1$ spatial dimensions to generate quantum error-correcting codes. For random stabilizer codes and the erasure channel, we find strong evidence that a depth $O(log N)$ random circuit is necessary and sufficient to converge (with high probability) to zero failure probability for any finite amount below the optimal erasure threshold, set by the channel capacity, for any $D$. Previous results on random circuits have only shown that $O(N^{1/D})$ depth suffices or that $O(log^3 N)$ depth suffices for all-to-all connectivity ($D to infty$). We then study the critical behavior of the erasure threshold in the so-called moderate deviation limit, where both the failure probability and the distance to the optimal threshold converge to zero with $N$. We find that the requisite depth scales like $O(log N)$ only for dimensions $D ge 2$, and that random circuits require $O(sqrt{N})$ depth for $D=1$. Finally, we introduce an expurgation algorithm that uses quantum measurements to remove logical operators that cause the code to fail by turning them into additional stabilizers or gauge operators. With such targeted measurements, we can achieve sub-logarithmic depth in $Dge 2$ below capacity without increasing the maximum weight of the check operators. We find that for any rate beneath the capacity, high-performing codes with thousands of logical qubits are achievable with depth 4-8 expurgated random circuits in $D=2$ dimensions. These results indicate that finite-rate quantum codes are practically relevant for near-term devices and may significantly reduce the resource requirements to achieve fault tolerance for near-term applications.
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.
We investigate the problem of synthesizing T-depth-optimal quantum circuits over the universal fault-tolerant Clifford+T gate set, where the implementation of the non-Clifford T-gate is the most expensive. We apply the nested-meet-in-the-middle(MITM) technique of Mosca,Mukhopadhyay(2020) and obtain a space-time trade-off to provably synthesize both depth and T-depth-optimal circuits. Specifically, using channel representation we design $Oleft(|mathbb{V}_n|^{leftlceilfrac{d}{c}rightrceil} right)$ time algorithm for T-depth-optimal circuits. $mathbb{V}_n$ is the set of some special T-depth-1 unitaries and $d$ is the minimum T-depth of input unitary. The MITM technique of Amy.et.al.(2013) has a complexity $left(left|mathcal{V}_nright|^{d/2}right)$, where $mathcal{V}_n$ is the set of T-depth-1 circuits. Since $|mathbb{V}_n| ll|mathcal{V}_{n}|$, our algorithm is much more efficient. For example, we take 2.152 seconds to generate $mathbb{V}_3$ (size 2282), Amy et al. takes about 4 days ($approx 3.5times 10^6$ seconds) to generate $mathcal{V}_{3}$ (size > 92,897,280). Inspired by the observations made by Mosca and Mukhopadhyay(2020), we design a $poly((log N)!,N,d)$ complexity heuristic algorithm for synthesizing T-depth-optimal circuits, where $N=2^n$. We synthesized previously unknown T-depth-optimal circuits for Fredkin, Peres, Negated-Toffoli and Quantum-XOR in $approx$ 27-28 minutes, and random 2 and 3-qubit unitaries with input T-depth in the range 2-20 and 2-7 respectively, and obtained output T-depth $leq$ input. There are no efficient T-depth-optimal synthesis algorithm to verify our results, but it is a good indication about the correctness of our claims for most unitaries.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
