Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe Role of Multiplicative Complexity in Compiling Low T-count Oracle Circuits
69
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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.
Based on the connection between the categorical derivation of classical programs from specifications and the category-theoretic approach to quantum physics, this paper contributes to extending the laws of classical program algebra to quantum programming. This aims at building correct-by-construction quantum circuits to be deployed on quantum devices such as those available at the IBM Q Experience. Quantum circuit reversibility is ensured by minimal complements, extended recursively. Measurements are postponed to the end of such recursive computations, termed quantamorphisms, thus maximising the quantum effect. Quantamorphisms are classical catamorphisms which, extended to ensure quantum reversibility, implement quantum cycles (vulg. for-loops) and quantum folds on lists. By Kleisli correspondence, quantamorphisms can be written as monadic functional programs with quantum parameters. This enables the use of Haskell, a monadic functional programming language, to perform the experimental work. Such calculated quantum programs prepared in Haskell are pushed through Quipper to the Qiskit interface to IBM Q quantum devices. The generated quantum circuits - often quite large - exhibit the predicted behaviour. However, running them on real quantum devices incurs into a significant amount of errors. As quantum devices are constantly evolving, an increase in reliability is likely in the near future, allowing for our programs to run more accurately.
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.
We construct quantum circuits which exactly encode the spectra of correlated electron models up to errors from rotation synthesis. By invoking these circuits as oracles within the recently introduced qubitization framework, one can use quantum phase estimation to sample states in the Hamiltonian eigenbasis with optimal query complexity $O(lambda / epsilon)$ where $lambda$ is an absolute sum of Hamiltonian coefficients and $epsilon$ is target precision. For both the Hubbard model and electronic structure Hamiltonian in a second quantized basis diagonalizing the Coulomb operator, our circuits have T gate complexity $O({N + log (1/epsilon}))$ where $N$ is number of orbitals in the basis. This enables sampling in the eigenbasis of electronic structure Hamiltonians with T complexity $O(N^3 /epsilon + N^2 log(1/epsilon)/epsilon)$. Compared to prior approaches, our algorithms are asymptotically more efficient in gate complexity and require fewer T gates near the classically intractable regime. Compiling to surface code fault-tolerant gates and assuming per gate error rates of one part in a thousand reveals that one can error correct phase estimation on interesting instances of these problems beyond the current capabilities of classical methods using only about a million superconducting qubits in a matter of hours.
Current quantum computers are especially error prone and require high levels of optimization to reduce operation counts and maximize the probability the compiled program will succeed. These computers only support operations decomposed into one- and two-qubit gates and only two-qubit gates between physically connected pairs of qubits. Typical compilers first decompose operations, then route data to connected qubits. We propose a new compiler structure, Orchestrated Trios, that first decomposes to the three-qubit Toffoli, routes the inputs of the higher-level Toffoli operations to groups of nearby qubits, then finishes decomposition to hardware-supported gates. This significantly reduces communication overhead by giving the routing pass access to the higher-level structure of the circuit instead of discarding it. A second benefit is the ability to now select an architecture-tuned Toffoli decomposition such as the 8-CNOT Toffoli for the specific hardware qubits now known after the routing pass. We perform real experiments on IBM Johannesburg showing an average 35% decrease in two-qubit gate count and 23% increase in success rate of a single Toffoli over Qiskit. We additionally compile many near-term benchmark algorithms showing an average 344% increase in (or 4.44x) simulated success rate on the Johannesburg architecture and compare with other architecture types.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
