Algorithm-aware (AlgAw) qubit mapping aims at directly providing the solutions to qubit mapping of algorithms with regular structures based on the algorithm's features. Although exact methods can provide high quality solutions, their compilation time grows exponentially with circuit size. To improve scalability, we propose the AlgAw qubit mapping approach. The main idea is to first identify subcircuits in an algorithm to be mapped, then analyze optimal solutions for small scale subcircuits found by exact methods, extend these solutions to large scale subcircuits, reconstruct the entire circuit and assign parameters, and finally map pretranspiled circuits onto the target quantum devices. Applying AlgAw to the quantum approximate optimization algorithm (QAOA) on linear and T-shaped subtopologies produces optimal and scalable solutions for arbitrary numbers of qubits and depths, which is critical to the algorithm's performance on near-term quantum devices. Compared to other methods including Qiskit, Tket, and SWAP-network, AlgAw produces the least number of CNOT gates and the lowest circuit depth for the pretranspiled circuits. Furthermore, AlgAw takes only a few seconds to construct a resulting circuit having a hundred qubits. The benchmarking results on IBM quantum devices show that AlgAw qubit mapping yields better performance than others. AlgAw is applicable to other variational quantum algorithms (VQAs) and can also be applied to other algorithms.
Algorithm-aware (AlgAw) qubit mapping aims at directly providing the solutions to qubit mapping of algorithms with regular structures based on the algorithm's features. Although exact methods can provide high quality solutions, their compilation time grows exponentially with circuit size. To improve scalability, we propose the AlgAw qubit mapping approach. The main idea is to first identify subcircuits in an algorithm to be mapped, then analyze optimal solutions for small scale subcircuits found by exact methods, extend these solutions to large scale subcircuits, reconstruct the entire circuit and assign parameters, and finally map pretranspiled circuits onto the target quantum devices. Applying AlgAw to the quantum approximate optimization algorithm (QAOA) on linear and T-shaped subtopologies produces optimal and scalable solutions for arbitrary numbers of qubits and depths, which is critical to the algorithm's performance on near-term quantum devices. Compared to other methods including Qiskit, Tket, and SWAP-network, AlgAw produces the least number of CNOT gates and the lowest circuit depth for the pretranspiled circuits. Furthermore, AlgAw takes only a few seconds to construct a resulting circuit having a hundred qubits. The benchmarking results on IBM quantum devices show that AlgAw qubit mapping yields better performance than others. AlgAw is applicable to other variational quantum algorithms (VQAs) and can also be applied to other algorithms.
Algorithm-aware (AlgAw) qubit mapping aims at directly providing the solutions to qubit mapping of algorithms with regular structures based on the algorithm’s features. Although exact methods can provide high quality solutions, their compilation time grows exponentially with circuit size. To improve scalability, we propose the AlgAw qubit mapping approach. The main idea is to first identify subcircuits in an algorithm to be mapped, then analyze optimal solutions for small scale subcircuits found by exact methods, extend these solutions to large scale subcircuits, reconstruct the entire circuit and assign parameters, and finally map pretranspiled circuits onto the target quantum devices. Applying AlgAw to the quantum approximate optimization algorithm (QAOA) on linear and T-shaped subtopologies produces optimal and scalable solutions for arbitrary numbers of qubits and depths, which is critical to the algorithm’s performance on near-term quantum devices. Compared to other methods including Qiskit, Tket, and SWAP-network, AlgAw produces the least number of CNOT gates and the lowest circuit depth for the pretranspiled circuits. Furthermore, AlgAw takes only a few seconds to construct a resulting circuit having a hundred qubits. The benchmarking results on IBM quantum devices show that AlgAw qubit mapping yields better performance than others. AlgAw is applicable to other variational quantum algorithms (VQAs) and can also be applied to other algorithms.
Algorithm-Aware (AlgAw) qubit mapping aims at directly providing the solutions to qubit mapping of algorithms with regular structures based on the algorithm’s features. Although the exact method provides a high-quality solution, its compilation time grows exponentially with the circuit size. To improve its scalability, we propose the AlgAw qubit mapping. The main idea is to first determine the subcircuits in an algorithm to be mapped, then analyze the optimal solutions of small-scale subcircuits found by exact methods to obtain solutions of large-scale subcircuits, and finally reconstruct the entire circuit and assign parameters. Applying AlgAw to the Quantum Approximate Optimization Algorithm (QAOA) on linear and T-shaped subtopologies produces optimal and scalable solutions for arbitrary numbers of qubits and depths, which is critical to the algorithm’s performance on Noisy Intermediate-Scale Quantum (NISQ) computers. Compared to Qiskit, Tket, and SWAP-Network, AlgAw produces the least number of CNOT gates and the lowest circuit depth. Furthermore, AlgAw takes only a few seconds to obtain a circuit with a hundred qubits that satisfies the connectivity constraints. The benchmarking results on Quantum Processing Units (QPUs) show that AlgAw qubit mapping yields higher values of approximation ratio than others. AlgAw can also be applied to other algorithms such as the Variational Quantum Eigensolver (VQE).
We propose a scalable, hierarchical qubit mapping and routing algorithm that harnesses the power of circuit synthesis. First, we decompose large circuits into subcircuits small enough to be directly resynthesized. For each block, we pre-synthesize them for all permutations of its input and output qubits. Following this offline step, we employ a permutation-aware, block-based generalization of the popular SABRE mapping algorithm. This mapping step stitches together blocks by choosing an input-output permutation that minimizes intrablock gate count and required inter-block communication (SWAP and bridge gates). Our approach has a twofold advantage: 1) circuit synthesis may eliminate more two-qubit gates than other optimizing compilers; 2) considering all permutations of input and output qubits eliminates communication operations transparently. In contrast, other mapping algorithms can only introduce communication operations. We show that we can produce better-quality circuits than commercial compilers: shorter by up to 68% (18% on average) fewer gates than Qiskit, up to 36% (9% on average) fewer gates than Tket. We outperform BQSkit, a permutation-unaware, synthesis-based compiler, by up to 67% (21% on average) fewer gates. We also exceed experimental optimal mappers such as OLSQ in quality (10.7% shorter circuits) and time to solution. Our scalable, heuristic approach can be seamlessly integrated into any quantum circuit compiler or optimization infrastructure, and it applies well to any qubit technology, such as superconducting and trapped ions.
Variational algorithms are among the first practical applications of quantum computing, but their performance is limited by today's noisy intermediate-scale quantum (NISQ) devices. The authors propose scalable, depth-optimal solutions to overcome these limitations by integrating optimal mapping algorithms applied to small submodules of a given NISQ computer (focusing on popular linear and T- and H-shaped subtopologies). Identification of the best qubits combined with postselection keeps the error rate in check. The team reports up to 82% reduction in circuit depth and an average of 138% better success probability, thus paving the way for reliable quantum computing ecosystems of tomorrow.
Quantum Approximation Optimization Algorithm (QAOA) is a highly advocated variational algorithm for solving the combinatorial optimization problem. One critical feature in the quantum circuit of QAOA algorithm is that it consists of two-qubit operators that commute. The flexibility in reordering the two-qubit gates allows compiler optimizations to generate circuits with better depths, gate count, and fidelity. However, it also imposes significant challenges due to additional freedom exposed in the compilation. Prior studies lack the following: (1) Performance guarantee, (2) Scalability, and (3) Awareness of regularity in scalable hardware. We propose a structured method that ensures linear depth for any compiled QAOA circuit on multi-dimensional quantum architectures. We also demonstrate how our method runs on Google Sycamore and IBM Non-linear architectures in a scalable manner and in linear time. Overall, we can compile a circuit with up to 1024 qubits in 10 seconds with a 3.8X speedup in depth, 17% reduction in gate count, and 18X improvement for circuit ESP.
Quantum algorithms can be expressed as quantum circuits when the circuit model of computation is adopted. Such a circuit description is usually hardware-agnostic, that is, it does not consider the limitations that the quantum hardware might have. In order to make quantum algorithms executable on quantum devices they need to comply to their constraints, which mainly affect the parallelism of quantum operations and the possible interactions between the qubits. The process of adapting a quantum circuit to meet the quantum chip restrictions is known as mapping. The resulting circuit usually has a higher number of gates and depth, decreasing the algorithm's reliability. Different mapping solutions have been already proposed. Most of them are meant for a specific quantum processor and differ in methodology, approach and features. In addition, they are usually only compared in terms of added gates, circuit depth and compilation time. No thorough comparative analysis of the different mapping solutions performance and features has been performed so far.In this paper, we propose to apply structured design space exploration (DSE) methodologies to the mapping procedures. This will allow not only to have a more in depth and structured analysis of their performance but also to identify what features are key and worth to implement. By using DSE we will be able to: i) determine in what regimes some mapping solutions outperform others; ii) derive optimal mapping strategies for specific quantum algorithms and quantum processors; and iii) perform an scalability analysis. In addition, DSE techniques cannot only be applied to the mapping layer that is key for bridging quantum applications to quantum devices, but also to the full-stack quantum computing system allowing for its crosslayer co-design.