REVIEW 7 cited by
Optimising quantum circuits is generally hard
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
abstract
In order for quantum computations to be done as efficiently as possible it is important to optimise the number of gates used in the underlying quantum circuits. In this paper we find that many gate optimisation problems for approximately universal quantum circuits are NP-hard. In particular, we show that optimising the T-count or T-depth in Clifford+T circuits, which are important metrics for the computational cost of executing fault-tolerant quantum computations, is NP-hard by reducing the problem to Boolean satisfiability. With a similar argument we show that optimising the number of CNOT gates or Hadamard gates in a Clifford+T circuit is also NP-hard. Again varying the same argument we also establish the hardness of optimising the number of Toffoli gates in a reversible classical circuit. We find an upper bound to the problems of T-count and Toffoli-count of $\text{NP}^{\text{NQP}}$. Finally, we also show that for any non-Clifford gate $G$ it is NP-hard to optimise the $G$-count over the Clifford+$G$ gate set, where we only have to match the target unitary within some small distance in the operator norm.
Forward citations
Cited by 7 Pith papers
-
CNOT-Distance is NP-complete under all-to-all connectivity
CNOT-Distance, deciding whether a given invertible binary matrix can be implemented with at most K CNOT gates under all-to-all connectivity, is NP-complete.
-
Linear-Time T-Gate Optimization via Random Abstraction
A randomized linear-time phase-folding algorithm using constant-width bitstring abstraction optimizes T-count in quantum circuits orders of magnitude faster than prior tools while achieving comparable reductions.
-
High-Precision Multi-Qubit Clifford+T Synthesis by Unitary Diagonalization
Search-based approximate diagonalization followed by analytical inversion yields high-precision multi-qubit Clifford+T circuits with 95% fewer non-Clifford gates on real-algorithm benchmarks.
-
Linear-Time T-Gate Optimization via Random Abstraction
A linear-time randomized static analysis that propagates constant-width bitstrings enables phase folding and T-count optimization matching SOTA tools on large circuits.
-
A Pathway to Practical Quantum Advantage in Solving Navier-Stokes Equations
A spectral-sparsity-based quantum solver is claimed to solve 2^80-cell Navier-Stokes problems in 42.6 days with 8.71 million physical qubits, a 1,100x speedup over a classical supercomputer.
-
Distributed Quantum Circuit Optimisation: Evaluating Global and Local encodings
Global optimization minimizes gate counts and compilation overhead in distributed quantum circuits, local optimization reduces non-local gates, and hybrid approaches balance both at the cost of much higher compilation time.
-
Distributed Quantum Circuit Optimisation: Evaluating Global and Local encodings
Global optimization minimizes gate counts and compilation overhead in distributed quantum circuits, local optimization reduces non-local communication even without explicit awareness, and hybrid balances both at much ...
Discussion (0). Sign in to comment.