Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userKnuth-Bendix Completion Algorithm and Shuffle Algebras For Compiling NISQ Circuits
197
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Compiling quantum circuits lends itself to an elegant formulation in the language of rewriting systems on non commutative polynomial algebras $mathbb Qlangle Xrangle$. The alphabet $X$ is the set of the allowed hardware 2-qubit gates. The set of gates that we wish to implement from $X$ are elements of a free monoid $X^*$ (obtained by concatenating the letters of $X$). In this setting, compiling an idealized gate is equivalent to computing its unique normal form with respect to the rewriting system $mathcal Rsubset mathbb Qlangle Xrangle$ that encodes the hardware constraints and capabilities. This system $mathcal R$ is generated using two different mechanisms: 1) using the Knuth-Bendix completion algorithm on the algebra $mathbb Qlangle Xrangle$, and 2) using the Buchberger algorithm on the shuffle algebra $mathbb Q[L]$ where $L$ is the set of Lyndon words on $X$.
rate research
Read More
We show the NP-completeness of the existential theory of term algebras with the Knuth-Bendix order by giving a nondeterministic polynomial-time algorithm for solving Knuth-Bendix ordering constraints.
Semidefinite Programming (SDP) is a class of convex optimization programs with vast applications in control theory, quantum information, combinatorial optimization and operational research. Noisy intermediate-scale quantum (NISQ) algorithms aim to make an efficient use of the current generation of quantum hardware. However, optimizing variational quantum algorithms is a challenge as it is an NP-hard problem that in general requires an exponential time to solve and can contain many far from optimal local minima. Here, we present a current term NISQ algorithm for SDP. The classical optimization program of our NISQ solver is another SDP over a smaller dimensional ansatz space. We harness the SDP based formulation of the Hamiltonian ground state problem to design a NISQ eigensolver. Unlike variational quantum eigensolvers, the classical optimization program of our eigensolver is convex, can be solved in polynomial time with the number of ansatz parameters and every local minimum is a global minimum. Further, we demonstrate the potential of our NISQ SDP solver by finding the largest eigenvalue of up to $2^{1000}$ dimensional matrices and solving graph problems related to quantum contextuality. We also discuss NISQ algorithms for rank-constrained SDPs. Our work extends the application of NISQ computers onto one of the most successful algorithmic frameworks of the past few decades.
The success of the current generation of Noisy Intermediate-Scale Quantum (NISQ) hardware shows that quantum hardware may be able to tackle complex problems even without error correction. One outstanding issue is that of coherent errors arising from the increased complexity of these devices. These errors can accumulate through a circuit, making their impact on algorithms hard to predict and mitigate. Iterative algorithms like Quantum Imaginary Time Evolution are susceptible to these errors. This article presents the combination of both noise tailoring using Randomized Compiling and error mitigation with a purification. We also show that Cycle Benchmarking gives an estimate of the reliability of the purification. We apply this method to the Quantum Imaginary Time Evolution of a Transverse Field Ising Model and report an energy estimation and a ground state infidelity both below 1%. Our methodology is general and can be used for other algorithms and platforms. We show how combining noise tailoring and error mitigation will push forward the performance of NISQ devices.
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.
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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
