Exact first-bit simulation of a polynomial-time classical program
ProvedInfoLossLAR.WorstCase.poly_program_first_bit_qptcomplexity-theorylar-regev-bridgequantum-computing
Let be a function on finite bit strings realized by a deterministic polynomial-time Boolean-stack program. There is a uniform quantum polynomial-time circuit family such that, for every input word ,
An empty output has acceptance probability zero. This gives an exact compiler interface for decision algorithms represented in the classical program model.
Preamble
import Definitions.Def_InfoLossLAR_WorstCase_QPT import Definitions.Def_QuantumMaxCutFiniteNumericRuntime set_option autoImplicit false open QAlgorithms.Complexity
Formal statement
namespace InfoLossLAR.WorstCase
theorem poly_program_first_bit_qpt (f : Str → Str) (hf : Nonempty (OAI.MetricKMedian.Binary.PolyProgram id id f)) :
∃ E : Family, IsQPT E ∧
∀ word : Str, acceptProb E word = if (f word)[0]? = some true then 1 else 0 := by
sorry
end InfoLossLAR.WorstCaseSource
Charles H. Bennett, Logical Reversibility of Computation, IBM Journal of Research and Development 17 (1973), pp. 525–532, reversible-simulation theorem, https://doi.org/10.1147/rd.176.0525. The concrete Boolean-stack input model, Clifford+T circuits, and first-bit acceptance statement are adaptations.