Blog

Optimizing quantum circuits is important. What makes it hard?

15
July
,
2022

Why should we optimize?

Optimizing quantum circuits allows extracting the most value from any given quantum hardware. There are many possible reasons why optimization may be important for a particular project. For instance:

  • Optimization that lowers the required quantum resources (e.g. the number of qubits, the number of two-qubit gates) can help fit a bigger problem into a given computer. If your organization can execute a given circuit today, whereas your competitor has to wait a year for a larger quantum computer, your organization just gained an advantage.
  • Because quantum computers are imperfect, creating shallower circuits could increase the accuracy of the results.
  • Optimized circuits could reduce the execution cost on cloud computers. We often see execution costs that depend, for instance, on the number of multi-qubit gates, so reducing this number helps reduce cost.

If optimization is important, how can we optimize quantum circuits?

Optimizing at the gate level

There are several useful optimizations that can be done at the gate level. These are done by transpilers and other tools that receive quantum assembly language code and make it better for a particular type of hardware.

One such optimization might be qubit swaps. Swap optimization takes into account the particular hardware topology: which qubits are next to each other. For instance, if in a given quantum circuit there are several operations (e.g. CNOT) that involve qubits 4 and 5, but in reality qubits 2 and 5 are better for two-qubit operations, the optimization might decide to swap qubits 4 and 2.

Another type of optimization might be to remove operations that cancel each other, such as two consecutive Hadamard gates or two consecutive X gates. In this case, the optimization might look like:

There are more sophisticated versions of this. For instance, here's an example:

Source: Brian Siegelwax post

While useful, gate-level optimizations are limited because to perform more sophisticated optimizations, they might need to understand the intent of the designer, or essentially automatically reverse-engineer the circuit. For instance, while a transpiler might be able to cancel out two consecutive Hadamard gates, it might not be able to detect and cancel out a QFT that's immediately followed by an inverse QFT. It will not be able to offer an alternative implementation of an adder, or suggest better ways to use additional qubits if they are available. A transpiler might not know that the designer wishes to minimize circuit depth, or use the minimum number of possible qubits.

What to do? Take a look at functional-level optimization.

Optimizing at the functional model level

Functional-level optimization does not have to 'reverse engineer' a circuit because it sees the design as a set of interconnected functions. It then generates a circuit based on what the designer defines as her optimization goals. A functional-model optimizer could do many things that a gate-level optimizer can't. Here are a few examples:

Explore alternative implementation of functional blocks

When you think about a functional block such as a quantum adder or a state preparation block, there might be several possible implementations for such a block. For instance, an adder might be implemented as a QFT adder or as a ripple adder. A optimizer at the functional model can choose the best one according to system-wide constraints. This point about system-wide constraints is important. While there may be an optimal implementation for any single block, it sometimes pays off to implement one block in a seemingly less efficient way if that way benefits other parts of the system. For instance, maybe using fewer qubits frees up these resources for another block which can be executed in parallel.

Use more or fewer auxiliary qubits

Imagine an MCX (multi-controlled Toffoli) gate. There are many ways to implement it when given more or fewer auxiliary qubits. See this discussion as an example. A functional-level optimizer can choose the right implementation based on the best allocation of system resources.

As an aside, the Classiq Coding Competition demonstrated many different ways to implement MCX gates.

Reuse qubits when necessary

A functional-model optimizer understands that inputs and outputs of each functional block as well as distinguish between output qubits that carry the output and auxiliary qubits that can be uncomputed and reused. For instance if function F has two useful outputs and one auxiliary qubit, that auxiliary qubit can be reused. Version "A" below uses nine total qubits for three instances of function F, but when only eight are available (version "B"), the auxiliary qubit from the second instance is reused. In version "C" there are even fewer qubits, and thus we see a cascading use of auxiliary qubits. This would be extremely difficult to detect and implement when using a gate-level model.

Modify the order of commutative operations

Version "A" below shows four Hamiltonian terms. Version "B" optimizes it by commuting their order. Understanding that this is a Hamiltonian allows a functional model to perform such optimization. BTW, here are many other examples of optimizing Hamiltonian exponentiation problems.

Summary

These were just a few of many potential examples. Others might include changing the circuit based on the noise model of the target platform, the desired accuracy, or many other variations.

Based on these and many others, I think it's fair to say that

it is self-evident that optimizing at higher levels of abstraction [e.g. at the functional level] is mathematically superior to optimizing at lower levels.

In short: optimization is important. High-quality optimization is very difficult to perform at the gate level, but it is no longer difficult when you work at the functional level and you use the right platform.

To see how the Classiq platform helps you create optimized and hardware-aware circuits with ease, schedule a demo with us.

Why should we optimize?

Optimizing quantum circuits allows extracting the most value from any given quantum hardware. There are many possible reasons why optimization may be important for a particular project. For instance:

  • Optimization that lowers the required quantum resources (e.g. the number of qubits, the number of two-qubit gates) can help fit a bigger problem into a given computer. If your organization can execute a given circuit today, whereas your competitor has to wait a year for a larger quantum computer, your organization just gained an advantage.
  • Because quantum computers are imperfect, creating shallower circuits could increase the accuracy of the results.
  • Optimized circuits could reduce the execution cost on cloud computers. We often see execution costs that depend, for instance, on the number of multi-qubit gates, so reducing this number helps reduce cost.

If optimization is important, how can we optimize quantum circuits?

Optimizing at the gate level

There are several useful optimizations that can be done at the gate level. These are done by transpilers and other tools that receive quantum assembly language code and make it better for a particular type of hardware.

One such optimization might be qubit swaps. Swap optimization takes into account the particular hardware topology: which qubits are next to each other. For instance, if in a given quantum circuit there are several operations (e.g. CNOT) that involve qubits 4 and 5, but in reality qubits 2 and 5 are better for two-qubit operations, the optimization might decide to swap qubits 4 and 2.

Another type of optimization might be to remove operations that cancel each other, such as two consecutive Hadamard gates or two consecutive X gates. In this case, the optimization might look like:

There are more sophisticated versions of this. For instance, here's an example:

Source: Brian Siegelwax post

While useful, gate-level optimizations are limited because to perform more sophisticated optimizations, they might need to understand the intent of the designer, or essentially automatically reverse-engineer the circuit. For instance, while a transpiler might be able to cancel out two consecutive Hadamard gates, it might not be able to detect and cancel out a QFT that's immediately followed by an inverse QFT. It will not be able to offer an alternative implementation of an adder, or suggest better ways to use additional qubits if they are available. A transpiler might not know that the designer wishes to minimize circuit depth, or use the minimum number of possible qubits.

What to do? Take a look at functional-level optimization.

Optimizing at the functional model level

Functional-level optimization does not have to 'reverse engineer' a circuit because it sees the design as a set of interconnected functions. It then generates a circuit based on what the designer defines as her optimization goals. A functional-model optimizer could do many things that a gate-level optimizer can't. Here are a few examples:

Explore alternative implementation of functional blocks

When you think about a functional block such as a quantum adder or a state preparation block, there might be several possible implementations for such a block. For instance, an adder might be implemented as a QFT adder or as a ripple adder. A optimizer at the functional model can choose the best one according to system-wide constraints. This point about system-wide constraints is important. While there may be an optimal implementation for any single block, it sometimes pays off to implement one block in a seemingly less efficient way if that way benefits other parts of the system. For instance, maybe using fewer qubits frees up these resources for another block which can be executed in parallel.

Use more or fewer auxiliary qubits

Imagine an MCX (multi-controlled Toffoli) gate. There are many ways to implement it when given more or fewer auxiliary qubits. See this discussion as an example. A functional-level optimizer can choose the right implementation based on the best allocation of system resources.

As an aside, the Classiq Coding Competition demonstrated many different ways to implement MCX gates.

Reuse qubits when necessary

A functional-model optimizer understands that inputs and outputs of each functional block as well as distinguish between output qubits that carry the output and auxiliary qubits that can be uncomputed and reused. For instance if function F has two useful outputs and one auxiliary qubit, that auxiliary qubit can be reused. Version "A" below uses nine total qubits for three instances of function F, but when only eight are available (version "B"), the auxiliary qubit from the second instance is reused. In version "C" there are even fewer qubits, and thus we see a cascading use of auxiliary qubits. This would be extremely difficult to detect and implement when using a gate-level model.

Modify the order of commutative operations

Version "A" below shows four Hamiltonian terms. Version "B" optimizes it by commuting their order. Understanding that this is a Hamiltonian allows a functional model to perform such optimization. BTW, here are many other examples of optimizing Hamiltonian exponentiation problems.

Summary

These were just a few of many potential examples. Others might include changing the circuit based on the noise model of the target platform, the desired accuracy, or many other variations.

Based on these and many others, I think it's fair to say that

it is self-evident that optimizing at higher levels of abstraction [e.g. at the functional level] is mathematically superior to optimizing at lower levels.

In short: optimization is important. High-quality optimization is very difficult to perform at the gate level, but it is no longer difficult when you work at the functional level and you use the right platform.

To see how the Classiq platform helps you create optimized and hardware-aware circuits with ease, schedule a demo with us.

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.

Start Creating Quantum Software Without Limits

contact us