Improved separation between quantum and classical computers for sampling and functional tasks

On approximation algorithms for# p

Larry Stockmeyer · 1985

Earlier work this paper cites.

Np is as easy as detecting unique solutions

Leslie G Valiant and Vijay V Vazirani · 1985

Earlier work this paper cites.

On the random-self-reducibility of complete sets, university of chicago technical report 90-22

J Feigenbaum and L Fortnow · 1990

Earlier work this paper cites.

Pp is as hard as the polynomial-time hierarchy

Seinosuke Toda · 1991

Earlier work this paper cites.

Designing programs that check their work

Manuel Blum and Sampath Kannan · 1995

Earlier work this paper cites.

Threshold computation and cryptographic security

Yenjo Han, Lane A Hemaspaandra, and Thomas Thierauf · 1997

Earlier work this paper cites.

New lowness results for zppnp and other complexity classes

V. Arvind and Johannes Köbler · 2002

Cited alongside, same era.

Quantum computing, postselection, and probabilistic polynomial-time

Scott Aaronson · 2005

Cited alongside, same era.

The complexity zoo, 2005

Scott Aaronson, Greg Kuperberg, and Christopher Granade · 2005

Cited alongside, same era.

The computational complexity of linear optics

Scott Aaronson and Alex Arkhipov · 2011

Cited alongside, same era.

The equivalence of sampling and searching

Scott Aaronson · 2014

Cited alongside, same era.

Power of quantum computation with few clean qubits

Original

Keisuke Fujii, Hirotada Kobayashi, Tomoyuki Morimae, Harumichi Nishimura, Shuhei Tamate, and Seiichiro Tani · 2015

Later among the works it cites.

Average-case complexity versus approximate simulation of commuting quantum computations

Michael J Bremner, Ashley Montanaro, and Dan J Shepherd · 2016

Later among the works it cites.

Hardness of classically sampling the one-clean-qubit model with constant total variation distance error

Tomoyuki Morimae · 2017

Later among the works it cites.

The weakness of ctc qubits and the power of approximate counting

Ryan O’Donnell and AC Cem Say · 2018

Later among the works it cites.

A polynomial-time classical algorithm for noisy random circuit sampling

Dorit Aharonov, Xun Gao, Zeph Landau, Yunchao Liu, and Umesh Vazirani · 2023

Later among the works it cites.