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

DOI10.1007/S00220-023-04720-XzbMATH Open1529.81044arXiv2205.06977OpenAlexW4375845706MaRDI QIDQ6109366FDOQ6109366

Authors:

Publication date: 28 July 2023

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

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.

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)

Cites Work

• Title not available (Why is that?)
• A mathematical introduction to compressive sensing
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Computational complexity and black hole horizons
• Title not available (Why is that?)
• Transcendental Numbers
• Random walks in compact groups
• Algebraic independence criteria.
• The Solovay--Kitaev algorithm
• A geometric approach to quantum circuit lower bounds
• A Boolean function requiring 3n network size
• A Lower Bound for the Formula Size of Rational Functions
• Efficient discrete approximations of quantum gates
• An application of Galois theory to elementary arithmetic
• Lower bounds for polynomial evaluation and interpolation problems
• 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)

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)