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

Yifan Jia, Michael M. Wolf

Type: Article

Publication Date: 2023-05-07

Citations: 1

DOI: https://doi.org/10.1007/s00220-023-04720-x

View Publication

Download PDF

Locations

Communications in Mathematical Physics - View
arXiv (Cornell University) - View - PDF

Similar Works

Action	Title	Year	Authors
+ PDF Chat	Quantum Circuits with Unbounded Fan-out	2003	Peter Høyer Robert Špalek
+ PDF Chat	Collapse of the Hierarchy of Constant-Depth Exact Quantum Circuits	2016	Yasuhiro Takahashi Seiichiro Tani
+	Superpolynomial Speedups Based on Almost Any Quantum Circuit	2008	Sean Hallgren Aram W. Harrow
+ PDF Chat	Complexity Bounds of Constant-Space Quantum Computation	2015	Tomoyuki Yamakami
+ PDF Chat	Diagonal quantum circuits: Their computational power and applications	2014	Yoshifumi Nakata Mio Murao
+ PDF Chat	Linear-depth quantum circuits for loading Fourier approximations of arbitrary functions	2023	Mudassir Moosa Thomas W. Watts Yiyou Chen Abhijat Sarma Peter L. McMahon
+ PDF Chat	Quantum Circuit Ansatz: Patterns of Abstraction and Reuse of Quantum Algorithm Design	2024	Xiaoyu Guo Takahiro Muta Jianjun Zhao
+ PDF Chat	Quantum branching programs and space-bounded nonuniform quantum complexity	2005	Martin Sauerhoff Detlef Sieling
+ PDF Chat	Quantum advantage with noisy shallow circuits	2020	Sergey Bravyi David Gosset Robert König Marco Tomamichel
+	Complexity Limitations on Quantum Computation	1999	Lance Fortnow John D. Rogers
+ PDF Chat	CutQC: Using Small Quantum Computers for Large Quantum Circuit Evaluations	2020	Wei Tang
+ PDF Chat	CutQC: Using Small Quantum Computers for Large Quantum Circuit Evaluations	2020	Wei Tang
+	Unbounded-error quantum computation with small space bounds	2011	Abuzer Yakaryılmaz A. C. Cem Say
+	Hay from the haystack: explicit examples of exponential quantum circuit complexity	2022	Yifan Jia Michael M. Wolf
+ PDF Chat	The Quantum Black-Box Complexity of Majority	2002	Thomas P. Hayes Samuel Kutin Dieter van Melkebeek
+	Quantum algorithms, quantum field theory, and computational complexity	2015	Keith Lee
+ PDF Chat	Finding broken gates in quantum circuits: exploiting hybrid machine learning	2020	Margarite L. LaBorde Allee C. Rogers Jonathan P. Dowling
+	Quantum Computational Complexity	2011
+	Quantum Cryptography at the Computational Frontier	2018	Romain Alléaume
+ PDF Chat	Polynomial time quantum computation with advice	2004	Harumichi Nishimura Tomoyuki Yamakami

Works That Cite This (2)

Action	Title	Year	Authors
+ PDF Chat	Preparation of Matrix Product States with Log-Depth Quantum Circuits	2024	Daniel Malz Georgios Styliaris Zhi-Yuan Wei J. I. Cirac
+	Extremal jumps of circuit complexity of unitary evolutions generated by random Hamiltonians	2025	Marcin Kotowski Michał Oszmaniec Michał Horodecki

Works Cited by This (13)

Action	Title	Year	Authors
+ PDF Chat	Random walks in compact groups	2013	Péter P. Varjú
+ PDF Chat	Transcendental Number Theory	1975	A. Baker
+ PDF Chat	Lieb-Robinson Bounds and the Generation of Correlations and Topological Quantum Order	2006	Sergey Bravyi M. B. Hastings Frank Verstraete
+ PDF Chat	Generating topological order: No speedup by dissipation	2014	Robert König Fernando Pastawski
+	Grands degrés de transcendance pour des familles d'exponentielles	1989	Guy Diaz
+ PDF Chat	Asymptotically Optimal Quantum Circuits for<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline"><mml:mi>d</mml:mi></mml:math>-Level Systems	2005	Stephen S. Bullock Dianne P. O’Leary Gavin K. Brennen
+	On the Linear Independence of Fractional Powers of Integers	1940	A. S. Besicovitch
+	An application of Galois theory to elementary arithmetic	1974	Ian Richards
+	Lower bounds for polynomial evaluation and interpolation problems	2002	Victor Shoup Roman Smolensky
+ PDF Chat	Computational complexity and black hole horizons	2016	Leonard Susskind