4.6 Article

Hay from the Haystack: Explicit Examples of Exponential Quantum Circuit Complexity

Journal

COMMUNICATIONS IN MATHEMATICAL PHYSICS
Volume 402, Issue 1, Pages 141-156

Publisher

SPRINGER
DOI: 10.1007/s00220-023-04720-x

Keywords

-

Ask authors/readers for more resources

The circuit complexity of the vast majority of quantum states and unitaries is exponential in the number of qubits. Similarly, their minimum description length is also exponentially large, making it difficult to find examples of exponential complexity. In this study, we present examples of constant description length but exponential circuit complexity. We provide infinite families of such examples, where each element requires an exponential number of two-qubit gates to be generated exactly from a product, and the same is true for the approximate generation of the majority of elements in the family. These results are based on sets with large transcendence degree and discussed in the context of tensor networks, diagonal unitaries, and maximally coherent states.
The vast majority of quantum states and unitaries have circuit complexity exponential in the number of qubits. In a similar vein, most of them also have exponential minimum description length, which makes it difficult to pinpoint examples of exponential complexity. In this work, we construct examples of constant description length but exponential circuit complexity. We provide infinite families such that each element requires an exponential number of two-qubit gates to be generated exactly from a product and where the same is true for the approximate generation of the vast majority of elements in the family. The results are based on sets of large transcendence degree and discussed for tensor networks, diagonal unitaries and maximally coherent states.

Authors

I am an author on this paper
Click your name to claim this paper and add it to your profile.

Reviews

Primary Rating

4.6
Not enough ratings

Secondary Ratings

Novelty
-
Significance
-
Scientific rigor
-
Rate this paper

Recommended

No Data Available
No Data Available