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 pi/2k, into an efficient fault-tolerant form using only Hadamard, controlled-{\\sc not}, and pi/8 gates. The algorithm runs in O(log2.71(1/epsilon)) time, and produces as output a sequence of O(log3.97(1/epsilon)) quantum gates which is guaranteed to approximate the desired quantum gate to an accuracy within epsilon>0. We also explain how the algorithm can be generalized to apply to multi-qubit gates and to gates from SU(d).
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).
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.