The Complexity of Quantum Circuit Mapping with Fixed Parameters

• URL: http://arxiv.org/abs/2207.08438v1
• Date: Mon, 18 Jul 2022 08:44:45 GMT
• Title: The Complexity of Quantum Circuit Mapping with Fixed Parameters
• Authors: Pengcheng Zhu, Shenggen Zheng, Lihua Wei, Xueyun Cheng, Zhijin Guan, Shiguang Feng
• Abstract summary: A quantum circuit must be preprocessed before implementing on NISQ devices. Quantum circuit mapping transforms the circuit into an equivalent one that is compliant with the NISQ device's architecture constraint. We give an exact algorithm for QCM, and show that the algorithm runs in time if the NISQ device's architecture is fixed.
• Score: 4.716951747614208
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A quantum circuit must be preprocessed before implementing on NISQ devices due to the connectivity constraint. Quantum circuit mapping (QCM) transforms the circuit into an equivalent one that is compliant with the NISQ device's architecture constraint by adding SWAP gates. The QCM problem asks the minimal number of auxiliary SWAP gates, and is NP-complete. The complexity of QCM with fixed parameters is studied in the paper. We give an exact algorithm for QCM, and show that the algorithm runs in polynomial time if the NISQ device's architecture is fixed. If the number of qubits of the quantum circuit is fixed, we show that the QCM problem is NL-complete by a reduction from the undirected shortest path problem. Moreover, the fixed-parameter complexity of QCM is W[1]-hard when parameterized by the number of qubits of the quantum circuit. We prove the result by a reduction from the clique problem. If taking the depth of the quantum circuits and the coupling graphs as parameters, we show that the QCM problem is still NP-complete over shallow quantum circuits, and planar, bipartite and degree bounded coupling graphs.

Related papers

• Quantum Compiling with Reinforcement Learning on a Superconducting Processor [55.135709564322624]
  We develop a reinforcement learning-based quantum compiler for a superconducting processor. We demonstrate its capability of discovering novel and hardware-amenable circuits with short lengths. Our study exemplifies the codesign of the software with hardware for efficient quantum compilation.
  arXiv  Detail & Related papers  (2024-06-18T01:49:48Z)
• ISAAQ: Ising Machine Assisted Quantum Compiler [3.8137985834223502]
  We propose ISing mAchine Assisted Quantum compiler (ISAAQ) to perform qubit routing with Ising machines. ISAAQ accurately estimates the compilation costs by updating itself using previous compilation results. ISAAQ exploits a cost-reduction method that implements commutative logical Controlled-NOT (CNOT) gates with fewer physical CNOT gates.
  arXiv  Detail & Related papers  (2023-03-06T01:47:10Z)
• Iterative Qubits Management for Quantum Index Searching in a Hybrid System [56.39703478198019]
  IQuCS aims at index searching and counting in a quantum-classical hybrid system. We implement IQuCS with Qiskit and conduct intensive experiments. Results demonstrate that it reduces qubits consumption by up to 66.2%.
  arXiv  Detail & Related papers  (2022-09-22T21:54:28Z)
• Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
  Multi-Object Tracking (MOT) is most often approached in the tracking-by-detection paradigm, where object detections are associated through time. As these optimization problems are often NP-hard, they can only be solved exactly for small instances on current hardware. We show that our approach is competitive compared with state-of-the-art optimization-based approaches, even when using of-the-shelf integer programming solvers.
  arXiv  Detail & Related papers  (2022-02-17T18:59:20Z)
• An Algebraic Quantum Circuit Compression Algorithm for Hamiltonian Simulation [55.41644538483948]
  Current generation noisy intermediate-scale quantum (NISQ) computers are severely limited in chip size and error rates. We derive localized circuit transformations to efficiently compress quantum circuits for simulation of certain spin Hamiltonians known as free fermions. The proposed numerical circuit compression algorithm behaves backward stable and scales cubically in the number of spins enabling circuit synthesis beyond $mathcalO(103)$ spins.
  arXiv  Detail & Related papers  (2021-08-06T19:38:03Z)
• A Quantum Dot Plot Generation Algorithm for Pairwise Sequence Alignment [0.0]
  Quantum Pairwise Sequence Alignment (QPSA) algorithm offers exponential speedups in data alignment tasks. It relies on an open problem of efficiently encoding the classical data being aligned into quantum superposition. We provide an alternative, explicit construction of this oracle called the Quantum Dot Plot (QDP) We evaluate QDP's operational complexity via analysis of the quantum machine instructions generated by the Q# and Qiskit software frameworks.
  arXiv  Detail & Related papers  (2021-07-23T16:48:29Z)
• Variational Quantum Eigensolver with Reduced Circuit Complexity [3.1158760235626946]
  We present a novel approach to reduce quantum circuit complexity in VQE for electronic structure calculations. Our algorithm, called ClusterVQE, splits the initial qubit space into subspaces (qubit clusters) which are further distributed on individual quantum circuits. The new algorithm simultaneously reduces the number of qubits and circuit depth, making it a potential leader for quantum chemistry simulations on NISQ devices.
  arXiv  Detail & Related papers  (2021-06-14T17:23:46Z)
• Automatically Differentiable Quantum Circuit for Many-qubit State Preparation [1.5662820454886202]
  We propose the automatically differentiable quantum circuit (ADQC) approach to efficiently prepare arbitrary quantum many-qubit states. The circuit is optimized by updating the latent gates using back propagation to minimize the distance between the evolved and target states. Our work sheds light on the "intelligent construction" of quantum circuits for many-qubit systems by combining with the machine learning methods.
  arXiv  Detail & Related papers  (2021-04-30T12:22:26Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  We show that it is possible to greatly reduce the number of qubits needed for the Traveling Salesman Problem. We also propose encoding schemes which smoothly interpolate between the qubit-efficient and the circuit depth-efficient models.
  arXiv  Detail & Related papers  (2020-09-15T18:17:27Z)
• Machine Learning Optimization of Quantum Circuit Layouts [63.55764634492974]
  We introduce a quantum circuit mapping, QXX, and its machine learning version, QXX-MLP. The latter infers automatically the optimal QXX parameter values such that the layed out circuit has a reduced depth. We present empiric evidence for the feasibility of learning the layout method using approximation.
  arXiv  Detail & Related papers  (2020-07-29T05:26:19Z)
• Supervised Learning Using a Dressed Quantum Network with "Super Compressed Encoding": Algorithm and Quantum-Hardware-Based Implementation [7.599675376503671]
  Implementation of variational Quantum Machine Learning (QML) algorithms on Noisy Intermediate-Scale Quantum (NISQ) devices has issues related to the high number of qubits needed and the noise associated with multi-qubit gates. We propose a variational QML algorithm using a dressed quantum network to address these issues. Unlike in most other existing QML algorithms, our quantum circuit consists only of single-qubit gates, making it robust against noise.
  arXiv  Detail & Related papers  (2020-07-20T16:29:32Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.