Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA quasi-polynomial time heuristic algorithm for synthesizing T-depth optimal circuits
118
0
0.0
(
0
)
Added by
Priyanka Mukhopadhyay Dr
Publication date
2021
fields
Physics
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
We consider the number of quantum queries required to determine the coefficients of a degree-d polynomial over GF(q). A lower bound shown independently by Kane and Kutin and by Meyer and Pommersheim shows that d/2+1/2 quantum queries are needed to solve this problem with bounded error, whereas an algorithm of Boneh and Zhandry shows that d quantum queries are sufficient. We show that the lower bound is achievable: d/2+1/2 quantum queries suffice to determine the polynomial with bounded error. Furthermore, we show that d/2+1 queries suffice to achieve probability approaching 1 for large q. These upper bounds improve results of Boneh and Zhandry on the insecurity of cryptographic protocols against quantum attacks. We also show that our algorithms success probability as a function of the number of queries is precisely optimal. Furthermore, the algorithm can be implemented with gate complexity poly(log q) with negligible decrease in the success probability. We end with a conjecture about the quantum query complexity of multivariate polynomial interpolation.
Let $C$ be a depth-3 arithmetic circuit of size at most $s$, computing a polynomial $ f in mathbb{F}[x_1,ldots, x_n] $ (where $mathbb{F}$ = $mathbb{Q}$ or $mathbb{C}$) and the fan-in of the product gates of $C$ is bounded by $d$. We give a deterministic polynomial identity testing algorithm to check whether $fequiv 0$ or not in time $ 2^d text{ poly}(n,s) $.
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.
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.
Recently Cristian S. Calude, Sanjay Jain, Bakhadyr Khoussainov, Wei Li and Frank Stephan proposed a quasi-polynomial time algorithm for parity games. This paper proposes a short proof of correctness of their algorithm.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
