Quantum Computing

Understanding the Complexity of Quantum Circuit Compilation

Share this post:

What’s a quantum circuit?

A quantum circuit can be a tricky thing. Quantum computing promises to be faster than classical computing in some, but not all computational problems. Whether quantum computers can be faster than classical computers depends on the nature of the problem being solved. When speedups are possible, the magnitude of the speedup also depends on the nature of the problem. For example, in certain types of problems, the solving time with quantum computing could reduce to about the square root of the solving time with classical computing. That is, a problem that would require one million operations on a classical computer might require 1,000 operations on a quantum computer.

What’s a qubit?

The basic memory units in a quantum computer are qubits, which are a generalization of the bits on a classical computer. A classical bit can take two distinct values, 0 and 1. At any given time, a bit has exactly one of these two values. As such, a bit is similar to a coin sitting on a table: it can be either in a head-up state (which we can consider to be the equivalent of a bit set to 0) or in the head-down position (bit set to 1). In contrast, a qubit can have more values than just 0 and 1. At a given time, the state of a qubit can be a combination of 0 and 1, called superposition. Using our coin analogy, superposition resembles a coin spinning in the air. Put informally, it’s like the qubit is in both basic states (0 and 1) at the same time. More formally, superposition is a weighted combination between the basic states 0 and 1.

How do quantum algorithms work?

Quantum algorithms work by applying quantum operations (called quantum gates) on subsets of qubits. Quantum gates are analogous to instructions in a classical program. A quantum algorithm represented using gates is called a quantum circuit.

Current models for quantum computing require quantum algorithms to be specified as quantum circuits on idealized hardware, ignoring details that could be specific to the actual hardware. This makes quantum algorithms more portable across different types of hardware, and it allows programmers to focus on the solution to the problem, not on the details specific to a given hardware.

Thus, a quantum program written by a human expert needs to be translated into a representation that a given quantum computer can execute. This is known as quantum circuit compilation (QCC). See the figure for an illustration. Compiling a quantum circuit requires adding additional gates that move qubit states to locations where the desired gate could act upon them under the physical constraints of the actual quantum processor. In a way, this is similar to how a classical program is compiled from a language that programmers understand (e.g., C++) into a binary representation that the hardware can execute.


Among potentially many compiled circuits that could correspond to a given quantum program, circuits with a shorter execution time are preferable. Part of the reason is a phenomenon known as decoherence: qubit states may get altered after a short time, due to factors such as interaction with the physical environment. For example, the commercial IBM 20-qubit environment has a coherence time of about 100 microseconds. Circuits with a shorter execution time could finish their running before decoherence occurs.

However, computing a compiled circuit with a shortest possible execution time could come at a cost. Specifically, the question is whether such compilations can be performed efficiently (i.e., in a reasonably short time). So far this has been an open question.

Recently, we published an article called “On the Complexity of Quantum Circuit Compilation” in the Symposium on Combinatorial Search, SoCS 2018. In this work we performed a comprehensive theoretical analysis of the difficulty of computing a compiled circuit with a shortest possible execution time.

We found that on certain types of circuits the problem is NP-complete. In other words, for some (but not all) instances of the problem, it could be very difficult to compile the input circuit in such a way that they will execute the program in the shortest possible time.

This is an important step forward in understanding the computational complexity of compiling quantum circuits so that they can be run efficiently on a given hardware configuration. Future work could study the complexity of other types of quantum circuit compilation problems. In addition, it is important to explore whether compiled circuits with a good execution time, but not necessarily optimal, can be computed efficiently all the time using bounded suboptimality algorithms. These algorithms can guarantee a certain gap between solution and best possible solution which does not exceed a given threshold.

Our theoretical results on the complexity of the quantum circuit compilation problem are very relevant to Qiskit. More specifically, Qiskit Terra provides the foundation of the quantum software stack to optimize the quantum circuits for a particular physical quantum device. Therefore, we envision a sustained effort on developing more efficient approximate compilation algorithms that also provide suboptimality guarantees.

To learn  more about quantum principles or create and run algorithms on real quantum computing hardware, visit the IBM Q Experience.


IBM Research – Ireland authors of “On the Complexity of Quantum Circuit Compilation”  L-R: Akihiro Kishimoto, Radu Marinescu, Adi Botea

More Quantum Computing stories

IBM Supports Q2Work Education Initiative

The need for a future workforce with a robust set of quantum computing skills drives our support for Q2Work, the National Science Foundation-funded initiative led by the University of Illinois and the University of Chicago to provide quantum education, programs, tools, and curricula to K-12 students.

Continue reading

Quantum Conundrum: Clifford Group Investigation Unexpectedly Reveals New Quantum Advantage Proof

When we began our current line of investigation, the goal was to study the structural property of the Clifford group, describing a set of transformations that generate entanglement, play an important role in quantum computing error correction, and are used in (randomized) benchmarking. In a series of one-thing-leads-to-another findings, however, we ended up discovering a new mathematical proof of quantum advantage – the elusive threshold at which quantum computers outperform classical machines in certain use cases.

Continue reading

IBM Roundtable: Building a Quantum Workforce Requires Interdisciplinary Education and the Promise of Real Jobs

The ability to harness quantum-mechanical phenomena such as superposition and entanglement to perform computation obviously poses a number of difficulties. Add in the need to make these systems perform meaningful work, and you’ve raised the stakes considerably. Creating a pipeline of talented, well-trained academics and professionals who can meet those challenges was the subject of IBM’s July 28 virtual roundtable, “How to Build a Quantum Workforce.” Watch the replay, here.

Continue reading