What is Compilation?
In quantum computing, compilation is the process of translating a high-level description of a quantum algorithm, described by algorithmic subroutines or general quantum gates, a sequence of low-level operations drawn from a predefined gate set, such as the Clifford + T set, that can be executed on a specific quantum device.
Challenges with compilation in Quantum Computing
Quantum computers have a set of gates that they can intrinsically implement, called native gates. To implement other gates, they need to decompose them onto this native set. The task of quantum compilers is to express a quantum algorithm with native gates only.
An important challenge in quantum compilation is to ensure that the compiled circuit is functionally equivalent to the original algorithm, while also optimizing it to achieve high fidelity when it’s implemented on noisy hardware.
Another challenge is to reduce the resource requirements of a circuit, such as its depth or gate count and qubit count. This is particularly important in quantum computing, because hardware is noisy and has limited coherence time, so larger and deeper circuits are more prone to errors.
Compilation techniques in Quantum Computing
Quantum computing requires specialized compilation techniques compared to classical computing.
One important class of methods is circuit transformation, where a circuit is rewritten using algebraic identities. In this approach, gates can be commuted, cancelled or combined according to simple rules. For example, Clifford gates map Pauli operators to Pauli operators under conjugation, and T gates commute with the Pauli Z gate but not with the Pauli X gate. These properties can be exploited to reduce the number of T gates, which are often costly in the fault-tolerant regime.
Moreover, a quantum circuit can be represented in multiple ways, such as a sequence of gates (gate-based formalism) or as graphical objects (e.g., ZX-calculus, or LOv-calculus for linear-optical circuits). Different representations enable different optimization techniques, which is why intermediate representations play a key role in quantum compilation.
In the context of error correction, it is often beneficial to express circuits in a gate set that matches the underlying fault-tolerant scheme. For example, Pauli-based computation is an efficient approach for certain error-corrected architectures.
Example with Quandela QPUs
At a high-level, a user can send an instruction on Quandela’s QPUs via Merlin or Perceval. This one can be represented as a photonic circuit, a unitary matrix or a gate-based circuit. Then we compile this circuit to a set of phases that needs to be applied on the QPU chip to implement that circuit. These phases are then transpiled to a set of voltages, as a voltage is what controls the tunable phase. There can be some gap between the voltage we should theoretically apply and the one we apply in practice, because the beam-splitters and phase-shifters are not perfectly manufactured. Maximising the fidelity between the input unitary and the transpiled unitary is a technique of error suppression.
With the first generation of QPUs at Quandela, the compilation starts with a photonic circuit and ends with a set of voltage to apply to the resistances of the photonic chip.
Frequently Asked Questions:
- What determines the “quality” of a compiled circuit?
The quality of a compiled circuit depends on the objective being optimized, and there is no single universal metric. Common criteria include:
- Circuit depth, which impacts decoherence and execution time
- Gate count, in particular 2-qubit gate count or T-gate count (which are especially costly in the fault-tolerant regime)
- Qubit count, as the use of auxiliary qubits can reduce circuit depth, leading to a trade-off between space and time resources
- Fidelity, reflecting how errors accumulate during execution
- Execution time / latency, including scheduling constraints
These metrics are often in tension (e.g., reducing depth may increase gate count), making compilation a multi-objective optimization problem.
References:
- Murali et al., Noise-Adaptive Compiler Mappings for NISQ Computers, ASPLOS 2019
- Cross et al., Validating quantum computers using randomized model circuits, PRA 2019
2. How hard is quantum compilation as a problem?
Quantum compilation is computationally hard, with several core subproblems known to be NP-hard, including qubit mapping, routing (SWAP insertion), and circuit optimization. The difficulty arises from the exponential search space, hardware constraints (connectivity, noise, timing), and competing optimization goals. As a result, finding optimal solutions is typically infeasible for realistic circuits. In practice, compilers rely on heuristics and approximation methods to produce good (but not optimal) solutions within reasonable time.
References:
- Li, Ding, Xie, Tackling the Qubit Mapping Problem for NISQ-Era Devices, ASPLOS 2019
- Zulehner et al., Mapping Quantum Circuits to IBM QX Architectures, IEEE TCAD 2018
- Herbert, A Survey of Quantum Compilers, arXiv:1808.03819