Competition Solutions: Hamiltonian Simulation of Lithium Hydride

In the recent Classiq Coding Competition, one of the challenges was a Hamiltonian Simulation problem. Below is a brief recap of the problem as well as some of the winning solutions.

Background:

One must first understand and simulate the quantum interactions at play to fully understand large quantum systems, such as complex molecules. Quantum simulation, also known as Hamiltonian simulation, is one of the most promising applications for quantum computers in the near future, with vast potential applications in drug discovery, materials research, and other fields.

The Hamiltonian Simulation problem describes the evolution of quantum systems, such as molecules and solid-state systems, by solving the Schrodinger equation. Quantum computers, as described in [LLOYD96], make it possible to scale up these simulations, vastly exceeding the capabilities of classical computers. In the near future, these simulations will facilitate rapid drug discovery, material development, and other endeavors. Using the Trotterization-based product formula is the most notable method for developing these kinds of simulations on a quantum computer.

Problem:

Using no more than ten qubits, generate a quantum circuit that approximates the evolution operator for Lithium Hydride (LiH) to within an error of 0.1 percent.  We made the problem more challenging by requiring contestants to use only CX and single-qubit gates.

Winning Metric:

To win, contestants needed to submit the smallest circuit depth possible without exceeding the defined error threshold of 0.1 percent.

FIRST PLACE - Diogo Cruz, Portugal

The winner of the Classiq Coding Competition's Hamiltonian Simulation problem was Diogo Cruz, of Portugal. A second-year doctoral student studying quantum computing, Diogo was recently featured on The Quantum Insider. To learn more about Diogo and his thoughts on the competition, click here. 

Using concepts from this paper on term grouping, Diogo designed his circuit by decomposing the LiH Hamiltonian into a graph and transforming this ostensibly complex problem into a straightforward clique-finding problem. Diogo conceptualized the problem as a set of circuits that measure quantum states in a particular basis. He then treated the terms of the Hamiltonian as nodes in a graph, where the edges between nodes indicate that the two terms commute with one another. Diogo then used the BronKerbosch algorithm to determine the minimum number of circuits required to measure the entire Hamiltonian, achieving a circuit depth of 671, which is truly remarkable.

For a Jupyter Notebook and a comprehensive explanation of the first-place Hamiltonian Simulation, see here.

SECOND PLACE - Konrad Deka, Poland

Konrad utilized multiple methods. By ordering the terms of the Hamiltonian by the absolute value of their coefficients, he selected and eliminated the terms with the lowest value. Then, by trotterization and reordering the terms of the Hamiltonian for maximal cancelation, Konrad was able to attain a circuit depth of 697.

For a Jupyter Notebook regarding the second-place Hamiltonian Simulation, see here.

THIRD PLACE - Janczar Knurek, Poland

Instead of dividing the Hamiltonian in half when implementing the Suzuki Trotter to simulate LiH, Janczar only divided the largest summands in half. Janczar also sorted the Hamiltonian by the absolute value of the coefficients and removed the smallest terms, a technique popular among the contestants. These techniques, along with a reimplementation of ZZZZ gates (which according to Janczar saved the circuit 60 depth), resulted in a circuit with a depth of 775.

For a Jupyter Notebook detailing the third-place Hamiltonian Simulation, see here.

FOURTH PLACE - Zeeshan Ahmed, India

Zeeshan initially employed a combination of Lexicographic, Interleave, and Magnitude Term Ordering to maximize gate cancelations. Further gate cancellations were accomplished by sorting the Hamiltonian terms by coefficient strength, both within and between groups. Then, by removing terms selectively and re-calibrating coefficients, Zeeshan achieved a gate depth of 1294 while maintaining an error bound of 0.1 percent.

For a Jupyter Notebook detailing the fourth-place Hamiltonian Simulation, see here.

For his complete explanation, see here.

FIFTH PLACE - Team Carnivorous Cacti (Tarushii Goel, Kareem Jaber, Cyril Sharma), USA

This intrepid group of high school students taught themselves Qiskit to implement their circuit and developed their own code to eliminate higher-order errors by rearranging the terms in the Hamiltonian. Team Carnivorous Cacti successfully completed the challenge with a circuit depth of 1411.

For a Jupyter Notebook regarding the fifth place Hamiltonian Simulation, see here.

‍

Here are the submitted circuit depth of the various valid solutions, sorted from best (lowest count) to the highest count:

Thank you to everyone who participated in and supported the Spring 2022 Classiq Coding Competition!