In quantum computing, a set of unitary gates forms a quantum circuit and performs a given task in polynomial time. Many well-known quantum algorithms employee a Boolean oracle, which is a subroutine required to detect a... [ view full abstract ]
In quantum computing, a set of unitary gates forms a quantum circuit and performs a given task in polynomial time. Many well-known quantum algorithms employee a Boolean oracle, which is a subroutine required to detect a solution of a given problem.
An oracle is often expressed as a function of input register states. However, the implementation of this black box is necessary to form a real circuit. Previous studies suggest several exact algorithms to synthesize the gate-level circuit satisfying given specifications, such as symbolic reachability analysis and Boolean satisfiability with SAT techniques. To the best of our knowledge, this work is the first attempt to apply the integer linear programming concept on this task.
In quantum circuit synthesis, there are several types of measuring circuit costs, such as speed, quantum cost, depth etc. The discrete optimization model introduced in this work solves a circuit synthesis problem of the given Boolean oracle with minimum depth. As many previous studies do, our study only considers Toffoli gates with multiple control bits and single target bit. The model also decides the location of target and control bits for each Toffoli gate.
Every multiple-control single-target Toffoli gate can be converted into a pairwise permutation matrix. [Figure 1] shows the example of how each Toffoli gate influences the input computational basis states(CBS).
We observed that the structure of a Toffoli gate directly decides which pair of CBS to be permutated. This property is utilized in building the proposed mathematical model, specifically on the constraint that expresses the functionality of each gates applied on the previous CBS. In doing so, defining the location of an empty bit, which is neither a target nor a control bit, plays a critical role as shown in [Figure 2].
Our experience with a preliminary computational benchmark data is also reported. The proposed model is expected to serve as a performance-benchmark tool to heuristic synthesis algorithms.
