ブログ
3
July
,
2022

The Classiq Coding Competition by the numbers

Share the article
Our library

How it started

When we launched the Classiq Coding Competition we did not know what to expect. We had several goals in mind:

  • Raise the awareness to the fact that compact and efficient were both important as well as possible.
  • Encourage innovation from all corners of the globe.
  • Encourage young adults to enter the quantum computing field.

As our CEO says:

“Creating efficient quantum algorithms is part engineering, part art. The Classiq Coding Competition is a call to the world’s quantum software community to showcase their talents and demonstrate how quantum computing can take humans to new heights. Efficient circuits enhance the ability of any quantum computer to solve important problems."

We tried to achieve these goals by specifying four quantum problems (state preparation, Hamiltonian exponentiation, constraint satisfaction and multi-controlled Toffoli gates) and offering various cash prizes for efficient solutions, original entries as well as 18-and-under participants.

What happened

The results exceeded our expectations:

  • 297 participants registered from 51 countries. The map below shows registrations by country.

Top countries were: India (71 registrations), United States (65), Israel (23), Germany (12), Canada (10), France (10), United Kingdom (9),  Spain (8), Japan (8) and Poland  (6 registrations).

  • About 10% of registrations (27 in total) were groups of people that banded together to solve the problems jointly.
  • 5% of registrations (14) were in the "18 and under" category.
  • 45% of those registered reported that they had less than 1 year of quantum computing experience, 32% reported 1-2 years of experience, 12% reported 2-3 years of experience and 11% reported over 3 years of experience.
  • Registrations came from both academia and industry. On the academic side, we received the full range of position: from undergraduate students to full professors. On the commercial side, we saw entries from people that work at IBM, Amazon, McKinsey, Infosys, Microsoft, Intel and many others.

Judging the solutions

We received a total of 146 solutions from 82 unique participants. The largest number of solutions were received for the multi-controlled Toffoli problem (57 solutions), followed by the constraint satisfaction problem (44), financial state preparation (23) and chemistry Hamiltonian exponentiation (22).

Our goal in the judging process was to determine the winners. While this may sound obvious, it is important to note that we thought of this as a competition, not an exam, so our goal was not to grade every solution but just to find the top ones. Thus, we went about it in the following way:

  • We sorted the solutions by the metric reported by the participants (number of CX gates or overall depth). Lower was better.
  • We checked the number of gates and overall depth. While most submissions reported this number accurately, some reported depth or gate counts that were a little higher or a little lower than the actual number.
  • We tested solutions starting from the lowest number. For each problem, we used a different test methodology. For instance, for the multi-controlled Toffoli problem, we used a circuit equivalence tool that allowed us to compare the solution to a standard implementation from a publicly-available library. For the constraint satisfaction, we executed the Grover circuit to determine the results, etc. For the log-normal state preparation function, we provided sample code to test the accuracy, etc.
  • For circuits that passed the verification, we looked deeper into the solution. For instance, we wanted to see that Grover solutions were not hard-coded and the circuit was actually implementing an oracle.
  • Many correct state preparation solutions had the same circuit depth, so we gave preference to those that submitted earlier in the competition.

Determining the winners in the 'innovative solution' and 'under 18' categories was more subjective, and we put emphasis on the effort, the quality of the explanation and so forth. Some of the explanations (see the constraint satisfaction winners) were detailed and formatted as if for an academic publication.

You can see the full list of winners here.

Financial: log-normal state preparation

The problem was defined as:

Many quantum algorithms rely on initializing qubits in a specific state. The promised speedup of the algorithm depends on the ability to prepare the quantum state efficiently. The challenge of preparing a quantum state is an example of a broader use case of compiling isometrics into specific quantum circuit and it is known that, in general, an exponential number of gates, are needed. One of the popular distributions is the log-normal distribution, used in many places such as in the Black-Scholes model option pricing formula.

The goal was to minimize the depth of the circuit and the winning solutions actually had a circuit depth of one. We will publish a post with more detailed explanations, but basically the problem had two degrees of freedom: the specific quantum gates that can be used to approximate the distribution, and the discretization (e.g. what each quantum bin corresponds to). By modifying the discretization, it was possible to achieve a quantum circuit depth of one. Here are the submitted circuit depth of the various valid solutions, sorted from best (lowest count) to the highest count:

A description of the winning solutions is here.

Chemistry: Hamiltonian exponentiation

The problem definition was:

The Hamiltonian Simulation problem describes the evolution of quantum systems, such as molecules and solid state systems, by solving the Schrodinger equation. Quantum computers enable the simulation in a scalable manner The most notable algorithm is the Trotterization-based product formula. For this problem, generate a circuit using no more than 10 qubits, that approximates the unitary e−iHeiH where HH is the qubit hamiltonian of a LiH (lithium hydride) molecule. The LiH Hamiltonian is composed of 276 Pauli strings. The approximation error is defined in the next section, and should be less than 0.1. The circuit should be composed of the CX and single qubit gates only.

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

A description of the winning solutions is here.

Optimization: constraint satisfaction

The problem was focused on solving a Kakuro puzzle:

Kakuro is a logic puzzle, often referred to as a mathematical transliteration of the crossword. The puzzle is played on a grid of filled and empty cells. The filled cells contain the required sum for the matching empty cells. The objective of the puzzle is to fill the empty spaces under two constraints: 1) Two cells on the same row/column cannot have the same number. 2) The sum of the cells on each row/column should equal the matching filled cell. The goal is to solve this Kakuro puzzle using Grover’s algorithm.

The winning solutions are presented and described here.

The results are shown below:

Multi-control Toffoli gate

The problem was defined as:

Many quantum operations include multi-controlled Toffoli (MCX) gates. Among the most notable are Grover Operator, logical AND operator, various state preparation algorithms, and arithmetic comparators.This task focuses on the implementation of the MCX gate with a limited qubit count and circuit depth. Your goal is to decompose an MCX gate with 14 control qubits into single-qubit and double-qubit CX gates. You may use up to five clean auxiliary qubits and should release (uncompute) them at the end of the circuit. Thus, the circuit can use no more than 20 total qubits: 14 control qubits, one target qubit, and up to five auxiliary qubits.

The winning solutions are described here and the ranked submissions are as follows:

The 18-and-under category

One of our pleasant surprises was the number and quality of submissions from younger participants. One team that is especially worthy of mention is team "Carnivorous Cacti" comprised of Tarushii Goel, Kareem Jaber, and Cyril Sharma, a team of three high school students that just graduated from Thomas Jefferson High School in Virginia. This team won the Bronze prize in the Toffoli decomposition problem (competing against the entire population), and also received a honorable mention in the Hamiltonian exponentiation problem. Naturally, we felt that they were deserving of an "18-and-under" prize.

Because we announced the winners during the Quantum.Tech conference in Boston, we asked the three students to join us in Boston and receive the prize in person. Here they are in our booth together with the prize:

I believe that the participants at the show were excited and optimistic about this new generation of quantum software engineers, and especially given the significant talent shortage that is facing the industry.

How it started

When we launched the Classiq Coding Competition we did not know what to expect. We had several goals in mind:

  • Raise the awareness to the fact that compact and efficient were both important as well as possible.
  • Encourage innovation from all corners of the globe.
  • Encourage young adults to enter the quantum computing field.

As our CEO says:

“Creating efficient quantum algorithms is part engineering, part art. The Classiq Coding Competition is a call to the world’s quantum software community to showcase their talents and demonstrate how quantum computing can take humans to new heights. Efficient circuits enhance the ability of any quantum computer to solve important problems."

We tried to achieve these goals by specifying four quantum problems (state preparation, Hamiltonian exponentiation, constraint satisfaction and multi-controlled Toffoli gates) and offering various cash prizes for efficient solutions, original entries as well as 18-and-under participants.

What happened

The results exceeded our expectations:

  • 297 participants registered from 51 countries. The map below shows registrations by country.

Top countries were: India (71 registrations), United States (65), Israel (23), Germany (12), Canada (10), France (10), United Kingdom (9),  Spain (8), Japan (8) and Poland  (6 registrations).

  • About 10% of registrations (27 in total) were groups of people that banded together to solve the problems jointly.
  • 5% of registrations (14) were in the "18 and under" category.
  • 45% of those registered reported that they had less than 1 year of quantum computing experience, 32% reported 1-2 years of experience, 12% reported 2-3 years of experience and 11% reported over 3 years of experience.
  • Registrations came from both academia and industry. On the academic side, we received the full range of position: from undergraduate students to full professors. On the commercial side, we saw entries from people that work at IBM, Amazon, McKinsey, Infosys, Microsoft, Intel and many others.

Judging the solutions

We received a total of 146 solutions from 82 unique participants. The largest number of solutions were received for the multi-controlled Toffoli problem (57 solutions), followed by the constraint satisfaction problem (44), financial state preparation (23) and chemistry Hamiltonian exponentiation (22).

Our goal in the judging process was to determine the winners. While this may sound obvious, it is important to note that we thought of this as a competition, not an exam, so our goal was not to grade every solution but just to find the top ones. Thus, we went about it in the following way:

  • We sorted the solutions by the metric reported by the participants (number of CX gates or overall depth). Lower was better.
  • We checked the number of gates and overall depth. While most submissions reported this number accurately, some reported depth or gate counts that were a little higher or a little lower than the actual number.
  • We tested solutions starting from the lowest number. For each problem, we used a different test methodology. For instance, for the multi-controlled Toffoli problem, we used a circuit equivalence tool that allowed us to compare the solution to a standard implementation from a publicly-available library. For the constraint satisfaction, we executed the Grover circuit to determine the results, etc. For the log-normal state preparation function, we provided sample code to test the accuracy, etc.
  • For circuits that passed the verification, we looked deeper into the solution. For instance, we wanted to see that Grover solutions were not hard-coded and the circuit was actually implementing an oracle.
  • Many correct state preparation solutions had the same circuit depth, so we gave preference to those that submitted earlier in the competition.

Determining the winners in the 'innovative solution' and 'under 18' categories was more subjective, and we put emphasis on the effort, the quality of the explanation and so forth. Some of the explanations (see the constraint satisfaction winners) were detailed and formatted as if for an academic publication.

You can see the full list of winners here.

Financial: log-normal state preparation

The problem was defined as:

Many quantum algorithms rely on initializing qubits in a specific state. The promised speedup of the algorithm depends on the ability to prepare the quantum state efficiently. The challenge of preparing a quantum state is an example of a broader use case of compiling isometrics into specific quantum circuit and it is known that, in general, an exponential number of gates, are needed. One of the popular distributions is the log-normal distribution, used in many places such as in the Black-Scholes model option pricing formula.

The goal was to minimize the depth of the circuit and the winning solutions actually had a circuit depth of one. We will publish a post with more detailed explanations, but basically the problem had two degrees of freedom: the specific quantum gates that can be used to approximate the distribution, and the discretization (e.g. what each quantum bin corresponds to). By modifying the discretization, it was possible to achieve a quantum circuit depth of one. Here are the submitted circuit depth of the various valid solutions, sorted from best (lowest count) to the highest count:

A description of the winning solutions is here.

Chemistry: Hamiltonian exponentiation

The problem definition was:

The Hamiltonian Simulation problem describes the evolution of quantum systems, such as molecules and solid state systems, by solving the Schrodinger equation. Quantum computers enable the simulation in a scalable manner The most notable algorithm is the Trotterization-based product formula. For this problem, generate a circuit using no more than 10 qubits, that approximates the unitary e−iHeiH where HH is the qubit hamiltonian of a LiH (lithium hydride) molecule. The LiH Hamiltonian is composed of 276 Pauli strings. The approximation error is defined in the next section, and should be less than 0.1. The circuit should be composed of the CX and single qubit gates only.

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

A description of the winning solutions is here.

Optimization: constraint satisfaction

The problem was focused on solving a Kakuro puzzle:

Kakuro is a logic puzzle, often referred to as a mathematical transliteration of the crossword. The puzzle is played on a grid of filled and empty cells. The filled cells contain the required sum for the matching empty cells. The objective of the puzzle is to fill the empty spaces under two constraints: 1) Two cells on the same row/column cannot have the same number. 2) The sum of the cells on each row/column should equal the matching filled cell. The goal is to solve this Kakuro puzzle using Grover’s algorithm.

The winning solutions are presented and described here.

The results are shown below:

Multi-control Toffoli gate

The problem was defined as:

Many quantum operations include multi-controlled Toffoli (MCX) gates. Among the most notable are Grover Operator, logical AND operator, various state preparation algorithms, and arithmetic comparators.This task focuses on the implementation of the MCX gate with a limited qubit count and circuit depth. Your goal is to decompose an MCX gate with 14 control qubits into single-qubit and double-qubit CX gates. You may use up to five clean auxiliary qubits and should release (uncompute) them at the end of the circuit. Thus, the circuit can use no more than 20 total qubits: 14 control qubits, one target qubit, and up to five auxiliary qubits.

The winning solutions are described here and the ranked submissions are as follows:

The 18-and-under category

One of our pleasant surprises was the number and quality of submissions from younger participants. One team that is especially worthy of mention is team "Carnivorous Cacti" comprised of Tarushii Goel, Kareem Jaber, and Cyril Sharma, a team of three high school students that just graduated from Thomas Jefferson High School in Virginia. This team won the Bronze prize in the Toffoli decomposition problem (competing against the entire population), and also received a honorable mention in the Hamiltonian exponentiation problem. Naturally, we felt that they were deserving of an "18-and-under" prize.

Because we announced the winners during the Quantum.Tech conference in Boston, we asked the three students to join us in Boston and receive the prize in person. Here they are in our booth together with the prize:

I believe that the participants at the show were excited and optimistic about this new generation of quantum software engineers, and especially given the significant talent shortage that is facing the industry.

About "The Qubit Guy's Podcast"

Hosted by The Qubit Guy (Yuval Boger, our Chief Marketing Officer), the podcast hosts thought leaders in quantum computing to discuss business and technical questions that impact the quantum computing ecosystem. Our guests provide interesting insights about quantum computer software and algorithm, quantum computer hardware, key applications for quantum computing, market studies of the quantum industry and more.

If you would like to suggest a guest for the podcast, please contact us.

量子ソフトウェア開発を開始

お問い合わせ