{'fraction_non_alphanumeric': 0.02772963604852686, 'fraction_numerical': 0.012709416522241479, 'mean_word_length': 5.391143911439114, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Lower bounds on the classical simulation of quantum circuits for quantum supremacy

Despite continued experimental progress, no task has
yet been performed on quantum technology that could not also have
been performed quickly on today's classical computers. One proposed
path toward achieving this milestone, which is often referred to as
quantum supremacy, is to perform specific types of quantum circuits
for which it is guaranteed, under plausible complexity theoretic
conjectures, that any classical approximate weak simulation
algorithm for these circuits must take more than polynomial time.
Instantaneous quantum (IQP) circuits and Quantum Approximate
Optimization Algorithm (QAOA) circuits are examples of circuits
with this guarantee under the assumption that the polynomial
hierarchy (PH) does not collapse. However, these arguments do not
communicate how large these quantum circuits must be built before
simulating them is hard in practice. We show how a fine-grained
version of this assumption involving the PH leads to a fine-grained
lower bound on the simulation time for IQP and QAOA circuits. Using
the lower bound, we conclude that IQP circuits must contain roughly
1700 qubits, and QAOA circuits must contain roughly 7100 qubits
before their simulation would be guaranteed to be intractable on
today's fastest supercomputers. Additionally, we apply the same
logic to find an asymptotic lower bound on the classical weak
simulation of Clifford + T circuits with n qubits, m Clifford
gates, and t T gates, concluding that any simulation with runtime
of the form poly(n;m)2[gamma]t must have [gamma] > 1/135
[approximately equal] 0:0074. The best existing algorithm of this
form [gamma] [approximately equal] 0:228.