By OpenAISourceGitHub

Manuscripts from openai/math

Fork
Clone
git clone https://openversions.com/git/index/openai-math.git
Cite
Version link
https://openversions.com/index/openai-math/commit/dfd8c46870b48511e697cbb43a3c8c91d375fa2f
Version identifier (commit hash)
dfd8c46870b48511e697cbb43a3c8c91d375fa2f

Fork to create your own copy with credit to the source. Clone to get a Git copy on your computer.

All papers

Claims

Findings

Regular trajectories, pruning and quantum parity

Fix positive integers d,k,Cd, k, C and a real 0<ε≤1/20 < \varepsilon \le 1/2. There is an integer n0=n0(d,k,C,ε)n_0 = n_0(d, k, C, \varepsilon) such that, for every n≥n0n \ge n_0, every allowed QAC0\mathrm{QAC}^0 circuit of depth at most dd on at most C(n+1)kC(n+1)^k total qubits (with ancillary qubits initialized to ∣0⟩|0\rangle, one output qubit measured, and all other final registers discarded without restriction) has an input x∈{0,1}nx \in \{0,1\}^n on which its answer equals PARITYn(x)\mathrm{PARITY}_n(x) with probability strictly less than 1/2+ε1/2 + \varepsilon.

No constant-depth, polynomial-resource QAC0\mathrm{QAC}^0 circuit can implement the coherent fanout operation Fn∣y1,…,yn,b⟩=∣y1⊕b,…,yn⊕b,b⟩F_n|y_1, \dots, y_n, b\rangle = |y_1 \oplus b, \dots, y_n \oplus b, b\rangle, including Moore's original formulation in which ancillary qubits must be restored to zero.

At each fixed depth and fixed polynomial total-qubit bound, for every fixed A>0A > 0, eventually every allowed unitary state preparation ρ\rho from all-zero inputs (with arbitrary final ancillas discarded) has felinity 2∑ypypyˉ<n−A2 \sum_y p_y p_{\bar{y}} < n^{-A}. For every fixed 0<δ<10 < \delta < 1, eventually every such preparation and every integer kk with nδ≤k≤n/2n^\delta \le k \le n/2 also satisfy 12∥ρ−∣Dkn⟩⟨Dkn∣∥1>180k\frac{1}{2} \|\rho - |D_k^n\rangle\langle D_k^n|\|_1 > \frac{1}{80k}.

For symmetric functions fn:{0,1}n→{0,1}f_n : \{0,1\}^n \to \{0,1\} with either ρ(fn)≥nδ\rho(f_n) \ge n^\delta for some fixed δ>0\delta > 0 or pointwise-error-1/31/3 approximate degree Ω(n1/2+η)\Omega(n^{1/2+\eta}) for some fixed η>0\eta > 0 (including strict majority MAJn\mathrm{MAJ}_n), no fixed-depth, polynomial-total-qubit QAC0\mathrm{QAC}^0 family achieves success at least 1/2+1/(log⁡n)γ1/2 + 1/(\log n)^\gamma on every input at every sufficiently large length, for any fixed γ>0\gamma > 0. Under the same circuit conventions, adjoining unit-cost primitive reversible unbounded threshold gates strictly enlarges the class computed with worst-case success at least 2/32/3.

Along a regular trajectory from ζ\zeta (∥ζ∥≤1\|\zeta\| \le 1) for a circuit VV with a bounded number of analytic layers, for any fixed 0<k<K<10 < k < K < 1 and any operator EE with deg⁡E≤mk\deg E \le m^k and ∥E∥≤exp⁡(mk)\|E\| \le \exp(m^k), there is eventually an operator E′E' such that ∥VEζ−E′Vζ∥≤exp⁡(−mk)\|V E \zeta - E' V \zeta\| \le \exp(-m^k), deg⁡E′≤mK\deg E' \le m^K, and ∥E′∥≤exp⁡(mK)\|E'\| \le \exp(m^K).

If VV has a bounded number of analytic layers, A,BA, B are product tests at its initial and final endpoints, χ=V†PBVψ\chi = V^\dagger P_B V \psi with ∥ψ∥≤1\|\psi\| \le 1, and both trajectories from ψ\psi and χ\chi are regular for VV, then an exp⁡(−mp)\exp(-m^p) tail bound on ψ\psi for HA≥mhH_A \ge m^h (for all b<h<1,0<p<hb < h < 1, 0 < p < h) implies the same tail bound on χ\chi.

Inserting an arbitrary product projection PBP_B at the output of a regular trajectory and evolving backwards preserves regularity.

For any sequence of circuits U=Ut⋯U1U = U_t \cdots U_1 on mm qubits with a bounded number tt of analytic layers and any normalized product starting states ψ0\psi_0, retaining at each reflection layer precisely the gates with projection probability ∥Pgψj−1∥2≥m−6\|P_g \psi_{j-1}\|^2 \ge m^{-6} on the exact pruned-prefix state ψj−1\psi_{j-1} produces a circuit WW with a regular trajectory from ψ0\psi_0 satisfying ∥Uψ0−Wψ0∥≤2tm−2\|U\psi_0 - W\psi_0\| \le 2tm^{-2}.

Methods

Product-reflection representation of generalized Toffoli gates Rg=I−2PgR_g = I - 2P_g and decomposition of each physical circuit layer into two analytic layers: a product of disjoint reflections and a tensor product of one-qubit unitaries.

Source excerpts

“An analytic layer will be either a product of such reflections on pairwise disjoint supports, or a tensor product of one-qubit unitaries. Splitting a physical layer into its two gate types preserves its operation, because its gates have disjoint supports. Thus a physical circuit of depth d gives at most 2d analytic layers.” · Show in paper

Asymptotic regularity condition for trajectory sequences, requiring exponentially decaying tails ∥1HS≥mhξj−1∥≤exp⁡(−mp)\|\mathbf{1}_{H_S \ge m^h} \xi_{j-1}\| \le \exp(-m^p) for every set SS of at most mbm^b reflections in a reflection layer.

Source excerpts

“The sequence of these trajectories is regular if the following holds at every reflection layer Uj: for every fixed triple 0 ≤ b < h < 1, 0 < p < h, eventually, simultaneously for every set S of at most mb gates of that layer, ∥1HS≥mh ξj−1∥ ≤ exp(−mp). (2.1)” · Show in paper

Integer zero filter Q(x)Q(x) constructed from normalized Chebyshev polynomials Sℓ(x)S_\ell(x) multiplied by exact roots ∏i=1a(1−x/i)\prod_{i=1}^a (1 - x/i) to approximate 1j=0\mathbf{1}_{j=0} on integers 0≤j≤mL0 \le j \le m^L while controlling global growth on [0,m][0, m].

Source excerpts

“Define Q(x) = Sℓ(x) ∏a i=1 (1 − x/i).” · Show in paper

Nonnegative tail detector polynomial T(x)=(MJ(1−Sℓ(x)2))2T(x) = (M_J(1 - S_\ell(x)^2))^2 constructed by composing a squared Chebyshev-based band indicator with the odd-degree majority polynomial MJM_J.

Source excerpts

“Take T(x) = (MJ(B(x)))2.” · Show in paper

State-dependent pruning rule that retains reflections in each layer whose projection probability on the exact pruned-prefix state satisfies ∥Pgψj−1∥2≥m−6\|P_g \psi_{j-1}\|^2 \ge m^{-6}.

Source excerpts

“Retain precisely the gates satisfying qg := ∥Pgψ∥2 ≥ m−6. (6.3)” · Show in paper

Reference-register copying of the uniform coherent input ∣+⟩⊗n|+\rangle^{\otimes n} via CNOTs to convert worst-case parity success into a signed acceptance expectation ⟨Φ,ZRPBΦ⟩≤−ε\langle \Phi, Z_R P_B \Phi \rangle \le -\varepsilon.

Source excerpts

“Attach a register R of n reference qubits, initially zero, and let COPY be the layer of disjoint CNOTs from input qubit Ii to reference qubit Ri. Our normalized product starting state is ψ0 = |+⟩⊗n I ⊗ |0⟩⊗a ⊗ |0⟩⊗n R” · Show in paper