Hay from the haystack: explicit examples of exponential quantum circuit complexity

DOI10.1007/S00220-023-04720-XMaRDI QIDQ6109366zbMATH OpenOpenAlexFDO

Authors

Publication date 28 July 2023

Published in Communications in Mathematical Physics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2205.06977

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Quantum computation (81P68) Two-body problems (70F05) Algebraic independence; Gel'fond's method (11J85) Matrix models and tensor models for quantum field theory (81T32) Quantum gates (81P65)

Abstract: 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.

Recommendations

• An algorithmic construction of quantum circuits of high descriptive complexity
• Quantum state description complexity (invited talk)
• State complexity and quantum computation
• How smooth is quantum complexity?
• ALGORITHMIC COMPLEXITY OF QUANTUM STATES

Cites work

• scientific article; zbMATH DE number 1579275 (Why is no real title available?)
• scientific article; zbMATH DE number 3906565 (Why is no real title available?)
• scientific article; zbMATH DE number 3465382 (Why is no real title available?)
• scientific article; zbMATH DE number 1776257 (Why is no real title available?)
• scientific article; zbMATH DE number 933466 (Why is no real title available?)
• A Boolean function requiring 3n network size
• A Lower Bound for the Formula Size of Rational Functions
• A geometric approach to quantum circuit lower bounds
• A mathematical introduction to compressive sensing
• Algebraic independence criteria.
• An application of Galois theory to elementary arithmetic
• Computational complexity and black hole horizons
• Efficient discrete approximations of quantum gates
• Epsilon-Nets, Unitary Designs, and Random Quantum Circuits
• Grands degrés de transcendance pour des familles d'exponentielles. (Large transcendence degrees for families of exponentials)
• Lower bounds for polynomial evaluation and interpolation problems
• Random walks in compact groups
• The Solovay--Kitaev algorithm
• Transcendental numbers

Cited in

(1)

• Extremal jumps of circuit complexity of unitary evolutions generated by random Hamiltonians

This page was built for publication: Hay from the haystack: explicit examples of exponential quantum circuit complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6109366)