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

Polynomial-Time Unitary Synthesis from a Boolean Oracle

There are a polynomial pp and a deterministic classical algorithm which, on input 1n1^n for any integer n≥1n \geq 1, outputs in time at most p(n)p(n) a quantum oracle circuit AnA_n using the gates H,T,T†,CNOTH, T, T^\dagger, \mathrm{CNOT} and a single Boolean oracle of input length m(n)≤p(n)m(n) \leq p(n), with total number of qubits, elementary gates, and oracle calls each at most p(n)p(n), such that for every unitary U∈U(2n)U \in U(2^n) there is a function f:{0,1}m(n)→{0,1}f : \{0,1\}^{m(n)} \to \{0,1\} for which the output channel Φn,f\Phi_{n,f} of AnOfA_n^{O_f} satisfies ∥Φn,f−U∥⋄≤1/2\|\Phi_{n,f} - \mathcal{U}\|_\diamond \leq 1/2.

For every unitary UU on Cd\mathbb{C}^d, there are unitaries PLP_{\mathrm{L}} and PRP_{\mathrm{R}} on Cd\mathbb{C}^d such that V=PLUPR=(ABCD)V = P_{\mathrm{L}} U P_{\mathrm{R}} = \begin{pmatrix} A & B \\ C & D \end{pmatrix} with ∥D∥≤r=3/4\|D\| \leq r = 3/4 and block sizes k,sk, s from (3.5), where PL,PRP_{\mathrm{L}}, P_{\mathrm{R}} and their inverses have implementations using O(n)O(n) programmable slots and O(n)O(n) clean working qubits with a structure determined by n,dn, d that works simultaneously for any family UλU_\lambda.

For the field maps EL,RL:Cd→CG⊗Ck\mathcal{E}_L, \mathcal{R}_L : \mathbb{C}^d \to \mathbb{C}^{\mathcal{G}} \otimes \mathbb{C}^k defined in (4.9), both satisfy (1−r2L)Id≤T∗T≤Id(1 - r^{2L}) I_d \leq \mathcal{T}^* \mathcal{T} \leq I_d and ∥F~EL−RLV∥≤2τ\|\widetilde{F}\mathcal{E}_L - \mathcal{R}_L V\| \leq 2\tau where τ=rL/(1−r)\tau = r^L / (1 - r), and in Fourier coordinates every row of EL\mathcal{E}_L and RL\mathcal{R}_L has at most LL nonzero entries.

Under the hypotheses and definitions of Section 4, there are exact-slot unitaries UE,UR\mathsf{U}_E, \mathsf{U}_R such that ∥UEι−ȷEL∥≤5r2L\|\mathsf{U}_E \iota - \jmath \mathcal{E}_L\| \leq 5 r^{2L} and ∥URι−ȷRL∥≤5r2L\|\mathsf{U}_R \iota - \jmath \mathcal{R}_L\| \leq 5 r^{2L}, each using O(L(K+n+h)+K)O(L(K + n + h) + K) slots and K+n+h+2K + n + h + 2 fresh qubits with slot structure independent of VV and working coherently with any additional label register.

For any n≥1n \geq 1, 1≤d≤2n1 \leq d \leq 2^n, and t≥0t \geq 0, there is a programmable-slot circuit structure, determined by n,d,tn, d, t and generated deterministically in time polynomial in n+tn + t, using t+O((n+1)10)t + O((n+1)^{10}) qubits and O((n+1)13)O((n+1)^{13}) slots, such that for every family (Uλ)λ∈{0,1}t(U_\lambda)_{\lambda \in \{0,1\}^t} of unitaries on Cd\mathbb{C}^d, its slot tables can be chosen to implement the controlled unitary UλU_\lambda, preserve the labels, and achieve clean-workspace operator norm error less than 1/1001/100.

There is an absolute positive integer KwK_{\mathrm{w}} such that every S∈SU(2)S \in SU(2) and every 0<ξ<10 < \xi < 1 admit a word in H,T,T†H, T, T^\dagger of length at most Kwξ−3K_{\mathrm{w}} \xi^{-3} whose matrix has determinant one and differs from SS by at most ξ\xi in operator norm.

Let a skeleton have SS slots on QQ qubits, and put η=1/h\eta = 1/h for an integer h≥2h \geq 2. There is a deterministic procedure, polynomial in Q,S,1/ηQ, S, 1/\eta, that produces a circuit over H,T,T†,CNOTH, T, T^\dagger, \mathrm{CNOT} and one Boolean oracle, with polynomially many qubits, gates, calls, and address bits, such that for every assignment of the slot tables, some contents of that oracle make the circuit differ from the prescribed skeleton by at most SηS\eta on inputs with its added scratch qubits zero, with the comparison circuit keeping those scratch qubits zero.

Methods

Programmable-slot circuit skeletons (uniformly controlled one-qubit gates) for label-controlled state preparation, basis permutations, and positive-phase Fourier transforms.

Source excerpts

“A programmable slot specifies one target qubit and an ordered list of other qubits as controls. Given a table of matrices Wy ∈ U(2), its action is ∑_{y∈{0,1}^c} |y⟩⟨y| ⊗ Wy, where c is the number of controls. A circuit skeleton specifies the registers, targets, and control lists of its slots, but leaves their tables unspecified.” · Show in paper

Sandwiching a unitary with permutations, Walsh-Hadamard transforms, and random diagonal sign matrices to produce a contracting internal block D with ∥D∥ ≤ 3/4.

Source excerpts

“Set Hq = H⊗log2qH^{⊗ log2 q}, and let W consist of its last s columns. We will choose diagonal sign matrices E1, E2 on C^q and use Hq E1 on the left and E2 Hq on the right, acting as the identity on the remaining d − q indices. The resulting internal block is D = W* E1 C', C' = M0 E2 W.” · Show in paper

Transfer-function feedback reduction F = A + BZ(I - DZ)^(-1)C with truncated Neumann series and power-sum frequency vectors v_i = (1, i, i^2, ..., i^L) to construct nearly isometric intertwining field maps with row-sparse Fourier matrices.

Source excerpts

“Number the internal coordinates by i = 1, . . . , s and put vi = (1, i, i^2, . . . , i^L) ∈ G, Z(z) = diag(χv1χ_{v1}(z), . . . , χvsχ_{vs}(z)).” · Show in paper

Amplitude amplification for row-sparse nearly isometric matrices using conditional column preparation and index erasure.

Source excerpts

“Starting with B, perform L rounds of (2BP0B* − I)(I − 2Q).” · Show in paper

Phase-sensitive SU(2) gate-word approximation and Boolean oracle lookup with exact reversible address and symbol uncomputation.

Source excerpts

“Use two bits to encode each symbol in {I, H, T, T†}. A single Boolean function stores all symbol bits at addresses containing (slot number, y, which word, word position, symbol bit).” · Show in paper