In quantum computing, the efficient optimization of Pauli string decompositions is a crucial aspect for the compilation of quantum circuits for many applications, such as chemistry simulations and quantum machine learning. In this paper, we propose a novel algorithm for the synthesis of trotterized time-evolution operators that results in circuits with significantly fewer gates than previous solutions. Our synthesis procedure takes the qubit connectivity of a target quantum computer into account. As a result, the generated quantum circuit does not require routing, and no additional CNOT gates are needed to run the resulting circuit on a target device. We compare our algorithm against Paulihedral and TKET, and show a significant improvement for randomized circuits and different molecular ansatzes. We also investigate the Trotter error introduced by our ordering of the terms in the Hamiltonian versus default ordering and the ordering from the baseline methods and conclude that our method on average does not increase the Trotter error.
In quantum computing, the efficient optimization of Pauli string decompositions is a crucial aspect for the compilation of quantum circuits for many applications, such as chemistry simulations and quantum machine learning. In this paper, we propose a novel algorithm for the synthesis of trotterized time-evolution operators that results in circuits with significantly fewer gates than previous solutions. Our synthesis procedure takes the qubit connectivity of a target quantum computer into account. As a result, the generated quantum circuit does not require routing, and no additional CNOT gates are needed to run the resulting circuit on a target device. We compare our algorithm against Paulihedral and TKET, and show a significant improvement for randomized circuits and different molecular ansatzes. We also investigate the Trotter error introduced by our ordering of the terms in the Hamiltonian versus default ordering and the ordering from the baseline methods and conclude that our method on average does not increase the Trotter error.
Hamiltonian simulation represents an important module in a large class of quantum algorithms and simulations such as quantum machine learning, quantum linear algebra methods, and modeling for physics, material science, and chemistry. One of the most prominent methods for realizing the time-evolution unitary is via the Trotter-Suzuki decomposition. However, there is a large class of possible decompositions for the infinitesimal time-evolution operator as the order in which the Hamiltonian terms are implemented is arbitrary. We introduce a perspective for generating a low-depth Trotter-Suzuki decomposition assuming the standard Clifford+rz gate set by adapting ideas from quantum error correction. We map a given Trotter-Suzuki decomposition to a constrained path on a graph which we deem the Pauli frame graph (PFG). Each node of the PFG represents the set of possible Hamiltonian terms currently available to be applied, Clifford operations represent a move from one node to another, and so the graph distance represents the gate cost of implementing the decomposition. The problem of finding the optimal decomposition is then equivalent to solving a problem similar to the traveling salesman. Although this is an NP-hard problem, we demonstrate the simplest heuristic, greedy search, and compare the resulting two-qubit gate count and circuit depth to more standard methods for a large class of scientifically relevant Hamiltonians, both fermionic and bosonic, found in chemical, vibrational, and condensed-matter problems which naturally scale. We find, in nearly every case we study, the resulting depth and two-qubit gate counts are less than those provided by standard methods, by as much as an order of magnitude. We also find the method is efficient and amenable to parallelization, making it scalable for problems of real interest.
Quantum simulation is the foundation for the design of many algorithms which share subroutines known as quantum simulation kernels. Optimizing the compilation of these kernels is crucial, involving two key components: 1) circuit synthesis and 2) qubit mapping. However, existing circuit synthesis methods either overlook qubit connectivity constraints (QCCs) or prioritize minimizing gate count over optimizing circuit depth. Similarly, current qubit mapping techniques do not work well with circuit synthesis methods. To address these limitations, we propose PauliForest, which comprises a connectivity-aware circuit synthesis algorithm and a Pauli-oriented qubit mapping algorithm. The synthesis algorithm employs heuristic strategies to generate shallower circuits, while the qubit mapping algorithm seamlessly collaborates with the circuit synthesis process. Compared to the state-of-the-art Paulihedral compiler, our approach significantly reduces both CNOT gate counts (by 13%) and circuit depths (by 25%). Experiments on a noisy simulator and a real superconducting quantum computer show that our algorithm can improve the fidelity of quantum circuit execution compared to Paulihedral.
Electronic Hamiltonian simulation is commonly formulated by mapping fermionic operators to qubit operators and subsequently expanding the resulting ladder-operator products into Pauli strings. While general, this procedure obscures the higher-level fermionic structure and can hide opportunities for circuit optimization. Building on ladder-string-pair (Lasp) diagonalization originally developed for Hamiltonian simulation of partial differential equations, we construct time-evolution circuits for the second-quantized electronic Hamiltonian without performing a Pauli expansion. For the most general case of complex-valued coefficients, we present a time-evolution circuit for a two-body fermionic Lasp operator that corresponds to 16 Pauli strings in the Pauli-expansion approach but does not suffer from Trotter error at this stage. Expanding the optimization scope from a single operator to a triad of three fermionic Lasp operators sharing the same four spin-orbital indices enables systematic cancellation of CX gates, reducing the CX-gate count from 36 to 12 in the example considered, still without introducing Trotter error at this stage. For n spin orbitals, further expanding the optimization scope to a sequence of O(n) suitably ordered triads enables a cascade of CX-gate reductions across triad boundaries, reducing the CX-gate count from O(n2) to O(n). The Lasp-based approach also naturally accommodates controlled time evolution and yields further optimizations for real-valued Hamiltonians. These results demonstrate that the Lasp-based approach enables more efficient time-evolution circuits by preserving high-level circuit structures and thereby expanding the scope of optimization, providing a systematic route toward more efficient electronic Hamiltonian simulation.
In designing quantum control, it is generally required to simulate the controlled system evolution with a classical computer. However, computing the time evolution operator can be quite resource consuming since the total Hamiltonian is often hard to diagonalize. In this paper, we mitigate this issue by substituting the time evolution segments with their Trotter decompositions, which reduces the propagator into a combination of single-qubit operations and fixed-time system evolutions. The resulting procedure can provide substantial speed gain with acceptable costs in the propagator error. As a demonstration, we apply the proposed strategy to improve the efficiency of the gradient ascent pulse engineering algorithm for searching optimal control fields. Furthermore, we show that the higher-order Trotter decompositions can provide efficient Ans\"atze for the variational quantum algorithm, leading to improved performance in solving the ground-state problem. The strategy presented here is also applicable for many other quantum optimization and simulation tasks.
Controlled time-evolution circuits select forward or backward Hamiltonian time evolution according to the state of an ancilla qubit. They are fundamental building blocks in quantum eigenvalue transformation of unitaries, Hamiltonian filtering, and related quantum algorithms. A direct realization adds ancilla control to the elementary gates of the time-evolution circuit and therefore increases the two-qubit gate count, compiled T depth and CX depth. We develop an efficient recursive algorithm that, for an arbitrary Pauli-sum Hamiltonian, partitions the input Pauli terms into groups and assigns to each group a sign-flip Pauli string that anti-commutes with the in-group terms, thereby removing ancilla control from the grouped time-evolution blocks. Numerical benchmarks on random Hamiltonians and structured spin Hamiltonians show reductions in compiled T depth and compiled CX depth. For a Kagome Hamiltonian with 24 spins under full connectivity, the proposed construction reduces the compiled T depth by 85.2% and the compiled CX depth by 68.9%, compared with a conventional implementation that decomposes the Hamiltonian into individual Pauli terms and implements the controlled time evolution of each term by directly adding the ancilla qubit to the corresponding Pauli-rotation circuit.
Recent advances in the development of quantum technology have made it possible to run small quantum programs on real quantum computers. This has created a need for compiling methods specific to these quantum computers. Unlike classical computers, if a quantum computation takes too long, the qubits might decohere and lose their information, making the computation useless. Hence, well-optimized quantum programs are a necessity. Like classical computers, quantum computers have registers for qubits that are generally sparsely connected. However, classical compilation methods that rely on copying data from one register to another do not apply to quantum computers because qubits cannot be copied. This problem is called the qubit routing problem. Following classical compilation, one could solve the connectivity constraints by moving the qubits to adjacent qubit registers. However, this requires the addition of SWAP gates throughout the quantum circuit, resulting in a strictly longer program. Additionally, a SWAP gate on qubits is not cheap and requires three CNOT gates each. Instead, in this thesis, we have defined a new method for quantum compilation that is based in the quantum nature of the program to be compiled. Instead of routing the qubits directly, we generate new machine code (in the form of quantum circuits) from an intermediate representation. We call this process quantum circuit synthesis. During synthesis, we make sure that all generated gates are supported by the target quantum hardware. Additionally, if the synthesis process is optimal, the resulting quantum circuit will also be optimal, although the methods proposed in this thesis are all heuristic in nature due to the computational complexity of optimal architecture-aware synthesis. We construct the nested intermediate representation starting from sequences of CNOT circuits interleaved with single qubit gates and incrementally generalize the intermediate representation to a universal representation. In particular, we propose two algorithms for synthesizing CNOT circuits from their parity matrix representation and one algorithm for synthesizing phase polynomials (i.e. CNOT+Rz circuits). Additionally, we show that when combining these methods into the universal representation called Mixed ZX-phase polynomial, it is competitive with existing commercial quantum compilers IBM's Qiskit and Quantinuum's TKET for large circuits. This thesis additionally contains a proposal for a framework to benchmark the quality of circuits used in an algorithm called Variational Quantum Eigensolver (VQE). This framework attempts to measure how close the solution found by the VQE is to our best estimate of a real molecule (i.e. accuracy), rather than a classical simulation of the approximate molecule as given to the quantum computer (i.e. precision).