Exact Quantum Circuit Optimization is co-NQP-hard

• URL: http://arxiv.org/abs/2510.16420v1
• Date: Sat, 18 Oct 2025 09:31:23 GMT
• Title: Exact Quantum Circuit Optimization is co-NQP-hard
• Authors: Adam Husted Kjelstrøm, Andreas Pavlogiannis, Jaco van de Pol,
• Abstract summary: We consider the natural problem of, given a circuit $C$, computing an equivalent circuit $C'$ that minimizes a quantum resource type.<n>We show that, when $C$ is expressed over any gate set that can implement the H and TOF gates exactly, each of the above optimization problems is hard for $textco-NQP$.
• Score: 4.554892610576937
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: As quantum computing resources remain scarce and error rates high, minimizing the resource consumption of quantum circuits is essential for achieving practical quantum advantage. Here we consider the natural problem of, given a circuit $C$, computing an equivalent circuit $C'$ that minimizes a quantum resource type, expressed as the count or depth of (i) arbitrary gates, or (ii) non-Clifford gates, or (iii) superposition gates, or (iv) entanglement gates. We show that, when $C$ is expressed over any gate set that can implement the H and TOF gates exactly, each of the above optimization problems is hard for $\text{co-NQP}$, and hence outside the Polynomial Hierarchy, unless the Polynomial Hierarchy collapses. This strengthens recent results in the literature which established an $\text{NP}$-hardness lower bound, and tightens the gap to the corresponding $\text{NP}^\text{NQP}$ upper bound known for cases (i)-(iii) over Clifford+T and (i)-(iv) over H+TOF circuits.

Related papers

• Clifford+V synthesis for multi-qubit unitary gates [0.0]
  We develop a general framework for synthesizing target gates by using a finite set of basic gates.<n>We introduce a suboptimal but short run-time algorithm for synthesizing multi-qubit controlled gates.
  arXiv  Detail & Related papers  (2025-10-09T14:57:55Z)
• Optimization and Synthesis of Quantum Circuits with Global Gates [41.99844472131922]
  We use global interactions, such as the Global Molmer-Sorensen gate present in ion trap hardware, to optimize and synthesize quantum circuits.<n>The algorithm is based on the ZX-calculus and uses a specialized circuit extraction routine that groups entangling gates into Global MolmerSorensen gates.<n>We benchmark the algorithm in a variety of circuits, and show how it improves their performance under state-of-the-art hardware considerations.
  arXiv  Detail & Related papers  (2025-07-28T10:25:31Z)
• Physics and Computation: A Perspective From Non-Hermitian Quantum Computer [8.73778121120948]
  We show that NQC is extraordinarily powerful, capable of solving not only all NP problems but also all problems within the complexity class $textPsharpP$ in time.<n>We investigate two physical schemes for implementing the non-unitary gate $G$ and find that the remarkable computational power of NQC originates from the exponentially large physical resources required.
  arXiv  Detail & Related papers  (2025-06-22T12:26:04Z)
• Characterizing randomness in parameterized quantum circuits through expressibility and average entanglement [39.58317527488534]
  Quantum Circuits (PQCs) are still not fully understood outside the scope of their principal application.<n>We analyse the generation of random states in PQCs under restrictions on the qubits connectivities.<n>We place a connection between how steep is the increase on the uniformity of the distribution of the generated states and the generation of entanglement.
  arXiv  Detail & Related papers  (2024-05-03T17:32:55Z)
• A multiple-circuit approach to quantum resource reduction with application to the quantum lattice Boltzmann method [39.671915199737846]
  We introduce a multiple-circuit algorithm for a quantum lattice Boltzmann method (QLBM) solve of the incompressible Navier--Stokes equations.<n>The presented method is validated and demonstrated for 2D lid-driven cavity flow.
  arXiv  Detail & Related papers  (2024-01-20T15:32:01Z)
• Optimising quantum circuits is generally hard [0.0]
  We find that many gate optimisation problems for approximately universal quantum circuits are NP-hard. We show that for any non-Clifford gate $G$ it is NP-hard to optimise the $G$-count over the Clifford+$G$ gate set.
  arXiv  Detail & Related papers  (2023-09-12T09:35:23Z)
• Direct pulse-level compilation of arbitrary quantum logic gates on superconducting qutrits [36.30869856057226]
  We demonstrate any arbitrary qubit and qutrit gate can be realized with high-fidelity, which can significantly reduce the length of a gate sequence. We show that optimal control gates are robust to drift for at least three hours and that the same calibration parameters can be used for all implemented gates.
  arXiv  Detail & Related papers  (2023-03-07T22:15:43Z)
• Approaching the theoretical limit in quantum gate decomposition [0.0]
  We propose a novel numerical approach to decompose general quantum programs in terms of single- and two-qubit quantum gates with a $CNOT$ gate count. Our approach is based on a sequential optimization of parameters related to the single-qubit rotation gates involved in a pre-designed quantum circuit used for the decomposition.
  arXiv  Detail & Related papers  (2021-09-14T15:36:22Z)
• Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
  We introduce a high-fidelity gate set inspired by a proposal for near-term quantum advantage in optimization problems. By orchestrating coherent, multi-level control over three transmon qutrits, we synthesize a family of deterministic, continuous-angle quantum phase gates acting in the natural three-qubit computational basis.
  arXiv  Detail & Related papers  (2021-08-03T17:49:09Z)
• Quantum supremacy and hardness of estimating output probabilities of quantum circuits [0.0]
  We prove under the theoretical complexity of the non-concentration hierarchy that approximating the output probabilities to within $2-Omega(nlogn)$ is hard. We show that the hardness results extend to any open neighborhood of an arbitrary (fixed) circuit including trivial circuit with identity gates.
  arXiv  Detail & Related papers  (2021-02-03T09:20:32Z)
• Cost-optimal single-qubit gate synthesis in the Clifford hierarchy [0.0]
  A synthesis algorithm can be used to approximate any unitary gate up to arbitrary precision. Current procedures do not yet support individual assignment of base gate costs.
  arXiv  Detail & Related papers  (2020-05-12T07:21:12Z)
• Improving the Performance of Deep Quantum Optimization Algorithms with Continuous Gate Sets [47.00474212574662]
  Variational quantum algorithms are believed to be promising for solving computationally hard problems. In this paper, we experimentally investigate the circuit-depth-dependent performance of QAOA applied to exact-cover problem instances. Our results demonstrate that the use of continuous gate sets may be a key component in extending the impact of near-term quantum computers.
  arXiv  Detail & Related papers  (2020-05-11T17:20:51Z)

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.