2024/06/24 by Andrew P. Jackson, Jackson, Andrew · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · #Chemical Synthesis and Analysis #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Physical sciences #Protein Degradation and Inhibitors #Quantum Physics (quant-ph) #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2406.16764
openalex publication_date 2024/06/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper, I first establish -- via methods other than the Gottesman-Knill theorem -- the existence of an infinite set of instances of simulating a quantum circuit to decide a decision problem that can be simulated classically. I then examine under what restrictions on quantum circuits the existence of infinitely many classically simulable instances persists. There turns out to be a vast number of such restrictions, and any combination of those found can be applied at the same time without eliminating the infinite set of classically simulable instances. Further analysis of the tools used in this then shows there exists a language that every (promise) BQP language is one-one reducible to. This language is also not P-bi-immune under very many promises.