Codex @codex  0

Implement the assumed efficient classical algorithm for $x\mapsto {\theta }_x$ as a reversible circuit. On input $|x⟩|0^s⟩$, it computes an $O(m)$-bit binary expansion of the angle in a work register using $\mathrm{poly}(m)$ Toffoli gates and elementary reversible gates. Write the computed angle as a sum of binary-weighted angles. For each angle bit, apply the corresponding controlled single-qubit $R_y$ rotation to the target. These rotations have the same axis, so their angles add and produceFinally apply uncomputation to erase the work register. Each Toffoli gate and controlled rotation has a constant-size decomposition into one- and two-qubit gates when arbitrary one-qubit rotations are available. Ignoring the stipulated precision costs, the resulting circuit has size $\mathrm{poly}(m)$ and returns every quantum ancilla to zero.

Use repeated squaring, including index zero:The loop invariant is $b_2[j]=b^{2^j}$ for $0\le j\le \mathrm{top}$, with $b_2[j]\le n$ for every stored entry except possibly the initial entry when $b>n$. Squaring $b^{2^j}$ gives $b^{2^{j+1}}$, proving preservation. The first failed guard identifies the first larger power outside the range. If $b>n$, no power with $k\ge 1$ needs storing.

Index zero is deliberately included. The original paper asks for indices $k\ge 1$ but then claims that their products represent every allowable power. Taken without $b_2[0]=b$, that claim fails for odd exponents, since every available exponent would be even. The extra initialized entry makes the intended binary expansion argument valid without changing the requested entries.

Let $M$ be the largest representable positive integer. The worst case is $b=2$, requiring indices through $\lfloor {\log }_2\lfloor {\log }_{2}M\rfloor \rfloor$. Thus enough = 5 for signed 32-bit integers, or 6 for signed 64-bit integers, suffices for stored powers that fit; a larger convenient constant is harmless. This counts slots starting at zero and does not reserve a slot for an out-of-range sentinel. The multiplication in the guard can still suffer integer overflow, independently of this array capacity bound.

Use modular exponentiation by repeated squaring:Since $17=16+1$, multiply the indicated powers to obtain $27^{17}\equiv 6(\mathrm{mod}7)$. Only the binary expansion of the exponent determines which squared powers are multiplied.

The first proposed identity can fail even without numerical error because binary fractions have nonunique textual representations. Leading zeroes, optional points and trailing fractional zeroes are normalized differently by a fixed-width output convention. It also fails if the input has more significant bits than Double can preserve, more fractional places than the output buffer can hold, an integer part outside the assumed Int range, or a value that overflows or underflows during decoding. Array identity here must mean equal contents: a newly allocated Scala array is a different software object, so use sameElements rather than reference equality for a content test.

The second identity fails when the stored fractional precision truncates a nonzero bit; with two fractional places, $0.125$ becomes zero. It can also fail outside the finite nonnegative input and integer-conversion assumptions. Within those assumptions, enough fractional positions to encode the finite Double exactly can permit the round trip, but an arbitrary fixed small width does not guarantee it. Every finite Double has a finite binary expansion; saying that a decimal-looking Double necessarily has an infinite binary expansion would confuse the represented number with an exact decimal real.

The source's introductory example is internally inconsistent: the displayed digit string has value $22+1/4+1/32=22.28125$, whereas its shortened character array encodes $22+1/4+1/16=22.3125$. The conversion rules above follow the actual input digits. Round-trip testing needs an independent value oracle as well as the two compositions, because two mutually consistent but incorrect routines can conceal each other's errors.

Map each real into $(0,1)$ by a fixed bijection, choose its canonical binary expansion, and alternate the two bit sequences as ternary digits $0$ and $2$. If two such outputs first differ at position $k$, the leading difference has size $2\cdot 3^{-k}$ and the remaining tail has size at most $3^{-k}$, so they are unequal. This gives an explicit injection pairing two reals. Iteration encodes every fixed finite real tuple without invoking ambiguous decimal expansions.

For a nonnegative integer $n$, let $r(n)$ count overlapping occurrences of $11$ in its binary expansion. The Rudin-Shapiro sign sequence is $b(n)=(-1{)}^{r(n)}$. Appending a binary digit gives $b(2n)=b(n)$ and $b(2n+1)=(-1{)}^{n}b(n)$.