This revision withdraws the claim, present in earlier circulated versions of this preprint, that FLQC renders Shor's algorithm physically unrealisable for RSA-2048 and sets an obstruction threshold at n* ≈ 100 bits (formerly §3.1). That argument rested on an invalid premise: that a single physical rotation gate must directly realise an exponentially small ideal phase angle. This is contradicted by established results in quantum-circuit compilation (Solovay–Kitaev/Ross–Selinger synthesis into a fixed discrete gate set; Coppersmith's approximate quantum Fourier transform) and by an explicit, quantitative treatment of exactly this question already in the peer-reviewed literature (Fowler & Hollenberg, Phys. Rev. A 70, 032329, 2004), which shows that factoring integers of thousands of bits requires no controlled rotation finer than - roughly 28 orders of magnitude coarser than the Δθmin estimate used throughout this work. The corrected argument is given in §3.1 and Part V.. Numerical simulation phase-resolution test protocol with qiskit: https://github.com/SergejMaterov/FLQC-Protocol
This revision withdraws the claim, present in earlier circulated versions of this preprint, that FLQC renders Shor's algorithm physically unrealisable for RSA-2048 and sets an obstruction threshold at n* ≈ 100 bits (formerly §3.1). That argument rested on an invalid premise: that a single physical rotation gate must directly realise an exponentially small ideal phase angle. This is contradicted by established results in quantum-circuit compilation (Solovay–Kitaev/Ross–Selinger synthesis into a fixed discrete gate set; Coppersmith's approximate quantum Fourier transform) and by an explicit, quantitative treatment of exactly this question already in the peer-reviewed literature (Fowler & Hollenberg, Phys. Rev. A 70, 032329, 2004), which shows that factoring integers of thousands of bits requires no controlled rotation finer than - roughly 28 orders of magnitude coarser than the Δθmin estimate used throughout this work. The corrected argument is given in §3.1 and Part V.. Numerical simulation phase-resolution test protocol with qiskit: https://github.com/SergejMaterov/FLQC-Protocol
This pedagogical review presents the proof of the Solovay-Kitaev theorem in the form of an efficient classical algorithm for compiling an arbitrary single-qubit gate into a sequence of gates from a fixed and finite set. The algorithm can be used, for example, to compile Shor's algorithm, which uses rotations of π/2k, into an efficient fault-tolerant form using only Hadamard, controlled-{\sc not}, and π/8 gates. The algorithm runs in O(log2.71(1/ϵ)) time, and produces as output a sequence of O(log3.97(1/ϵ)) quantum gates which is guaranteed to approximate the desired quantum gate to an accuracy within ϵ>0. We also explain how the algorithm can be generalized to apply to multi-qubit gates and to gates from SU(d).
Typical circuit implementations of Shor's algorithm involve controlled rotation gates of magnitude $\ensuremath{\pi}∕{2}^{2L}$ where L is the binary length of the integer N to be factored. Such gates cannot be implemented exactly using existing fault-tolerant techniques. Approximating a given controlled $\ensuremath{\pi}∕{2}^{d}$ rotation gate to within $\ensuremath{\delta}=O(1∕{2}^{d})$ currently requires both a number of qubits and a number of fault-tolerant gates that grows polynomially with d. In this paper we show that this additional growth in space and time complexity would severely limit the applicability of Shor's algorithm to large integers. Consequently, we study in detail the effect of using only controlled rotation gates with d less than or equal to some dmax. It is found that integers up to length Lmax=O(4dmax) can be factored without significant performance penalty implying that the cumbersome techniques of fault-tolerant computation only need to be used to create controlled rotation gates of magnitude $\ensuremath{\pi}∕64$ if integers thousands of bits long are desired factored. Explicit fault-tolerant constructions of such gates are also discussed.
This note connects two claims in the Quantumograph program. The Computational Reducibility Theorem shows that a finite unitary quantum graph is, in principle, exactly forecastable from one spectral slice: the state at one time together with the spectrum of the evolution operator. The Fundamental Limit of Quantum Computation (FLQC) adds a physical constraint: any realizable quantum device has a finite phase resolution, so exact spectral data and exact phase gates cannot be implemented with arbitrary precision. Realism, in this setting, is the position between these two statements. The universe is computable in principle, but nature imposes a nonzero floor on the precision with which that computability can be instantiated. The note derives the phase floor, compares it with the phase resolution required by QFT- and Shor-type circuits, and gives a concrete experimental signature on superconducting quantum processors.
The paper proposes a new category of limitation on quantum computation distinct from decoherence, control error, and algorithmic complexity arising from the discreteness of an underlying periodic gauge-graph model of spacetime, and derives it explicitly as εF ≳ 2π/L from single-valuedness of the U(1) holonomy on the graph. We quantify the bound against the phase precision required by Shor's algorithm across several RSA key sizes, showing the gap is too large for any near-term cryptographic relevance, and we identify the physically meaningful, testable content as a saturation of residual phase error with hardware scale rather than the underlying cosmological number itself. What we believe is new here is the derivation: rather than asserting a fundamental limit by analogy with other Planck-scale arguments, we obtain it as a direct structural consequence of a specific lattice model and give a falsifiable laboratory protocol (Sec. V) for testing it on existing superconducting processors.
There are two important, and potentially interconnecting, avenues to the realization of large-scale quantum algorithms: improvement of the hardware, and reduction of resource requirements demanded by algorithm components. In focusing on the latter, one crucial subroutine to many sought-after applications is the quantum adder. A variety of different implementations exist with idiosyncratic pros and cons. One of these, the Draper quantum Fourier adder, offers the lowest qubit count of any adder, but requires a substantial number of gates as well as extremely fine rotations. In this work we present a modification of the Draper adder which eliminates small-angle rotations to highly coarse levels, matched with some strategic corrections. This reduces hardware requirements without sacrificing the qubit saving. We show that the inherited loss of fidelity is directly given by the rate of carry and borrow bits in the computation. We derive formulas to predict this, complemented by complete gate-level matrix product state simulations of the circuit. Moreover, we analytically describe the effects of possible stochastic control error. We present an in-depth analysis of this approach in the context of Shor's algorithm, focusing on the factoring of RSA-2048. Surprisingly, we find that each of the $7\ifmmode\times\else\texttimes\fi{}{10}^{7}$ quantum Fourier transforms may be truncated down to $\ensuremath{\pi}/64$, with additive rotations left only slightly finer. This result is much more efficient than previously realized. We quantify savings in terms of both logical resources and raw magic states, demonstrating that phase adders can be competitive with Toffoli-based constructions.
In the world of quantum computing, quantum Fourier transform (QFT) has been one of the most important subroutines for quantum algorithms, as exemplified by Shor's factoring algorithms and phase estimation (which in itself has been used as a primitive in various quantum algorithms). In fact most of the well known quantum algorithms can be divided into two classes, QFT based algorithms and search based algorithms. The usual circuit for QFT (covered in almost every basic quantum algorithms course) needs O(q2) gates (and O(q) qubits) to perform the exact Fourier transform over F2q. Cleve and Watrous (FOCS 2000) improved this gate count to O(q(logq)2(loglogq)) using the integer multiplication algorithm in O(n(logn)(loglogn)) time for two n-bit integers (best known at that time). Our first main result shows that this gate count can be improved to O(q(logq)). In fact, if there is a multiplication circuit, to multiply two n-bit integers, with O(n(logn)α) gates; we get a QFT circuit with O(q(logq)α) gates (improving upon O(q(logq)α+1)) gates from the construction of Cleve and Watrous). Given the recent claim by OpenAI about integer multiplication, this opens up the possibility of having a QFT circuit with o(q(logq)) gates. On approximating the QFT over $\ZZ/(2^q \ZZ)$, the result of Ahokas, Cleve and Hales (ERATO 2003) showed that an approximating circuit can be built with O(q(loglog(q/ε))α+1) gates, where ε is the approximating parameter. Our second main result again improves this to O(q(loglog(q/ε))α) gates.