Factoring an integer with three oscillators and a qubit

Domain: physics
Published: 2025-12-26
Editorial outcome: accept

Abstract
A common starting point of traditional quantum algorithm design is the notion of a universal quantum computer with a scalable number of qubits. This convenient abstraction mirrors classical computations manipulating bits. It allows for a device-independent development of algorithmic primitives. Here we argue that an alternative approach centered on the physical setup can yield great benefits. As an example, we consider hybrid qubit-oscillator systems with linear optics operations augmented by certain qubit-controlled Gaussian unitaries. The continuous variable Fourier transform and certain arithmetic operations have native realizations in such systems. We put this to algorithmic use and give a polynomial-time quantum factoring algorithm which uses only one qubit and three oscillators, independent of the number being factored.

Introduction
The notion of a universal, scalable quantum computer as succinctly formulated by DiVincenzo’s criteria1 stipulates that a computationally useful quantum device needs to provide a number of (logical) qubits scaling extensively with the problem size. Following this idea, the most established current approach to quantum computing with continuous-variable (CV) systems (that have a long history, see e.g., refs. 2–9) is to encode a single logical qubit in a suitable two-dimensional subspace of a bosonic mode. By associating a single physical information carrier (an oscillator) to each individual qubit, this philosophy emphasizes modularity, breaking the engineering challenge into more manageable pieces, and allowing for device-independent approaches in algorithms design. It amounts to a quite literal interpretation of what it means to scale a quantum computation.

Here, we argue that in light of the possibilities offered by CV quantum systems, this simple and seemingly inevitable idea of scalability may be too restrictive. Specifically, consider Shor’s integer factoring algorithm10: Following the standard paradigm, it requires a number of qubits that is proportional to the number of bits specifying the integer to be factored. With our alternative approach, we can show that, instead, only three oscillators and a qubit suffice to efficiently factor any arbitrarily large integer N: We give a quantum algorithm which factors an n-bit integer (for any integer n) using a polynomial number of elementary operations which are readily available in present-day experimental setups. In other words, our algorithm trades problem size (length n of the binary representation of the integer to be factored) against circuit size (i.e., number of gates) while keeping the underlying physical system (three oscillators and one qubit) fixed. Since any finite-dimensional space can trivially be embedded into a single harmonic oscillator—the question of how to realize a computation with a small number of CV information carriers is only meaningful when restricting to basic, physically realizable operations, and with an estimate on the number of operations used.

Results
The qubit-oscillator model of computation
The set of elementary operations we consider is a subset of the toolbox available in hybrid qubit-oscillator systems, see ref. 11 for an up-to-date review including a discussion of physical realizations. Concretely, we count as one elementary operation each of the following:

(i) Preparation of the computational basis state |0> of the qubit, and of the single-mode vacuum state |vac> on any of the three modes.
(ii) Clifford gates on the qubit, and single-mode phase space rotations, translations, squeezing, as well as two-mode beam splitters (on any pair of modes), with parameters (such as angles) bounded by a constant.
(iii) Qubit-controlled phase space displacements, and qubit-controlled phase space rotations, with parameters bounded by a constant.
(iv) Computational basis measurement on the qubit and homodyne quadrature measurements on the bosonic modes.

The unitaries (iii) are generated by Jaynes-Cummings-type Hamiltonians (see e.g., refs. 12–14) and enable the realization of non-Gaussian operations on the oscillators. An example is the preparation of approximate, i.e., finitely squeezed, Gottesman-Kitaev-Preskill (GKP) states15, defined as follows (for convenience, our convention differs slightly from the literature, where peaks are typically centered on integer multiples of \sqrt{2\pi} instead of integers):

GKP_{\kappa, \Delta}(x) \propto \sum_{z \in Z} e^{-\kappa^2 z^2/2} e^{-(x-z)^2/(2\Delta^2)} for x \in R,

where \kappa, \Delta > 0. In ref. 16, we give a protocol PG_{\kappa, \Delta} achieving this with a constant success probability (which can be amplified by repetition to an arbitrary constant without change in complexity), polynomial error in trace distance in (\kappa, \Delta), and a number of elementary operations which is linear in (log 1/\kappa, log 1/\Delta), see Theorem 2.2 in the Supplementary Note for details.

Description of the factoring algorithm
The elementary operations (ii), (iii) can be used to realize certain (real) arithmetic operations when the action on bosonic position-eigenstates |x>, x \in R and qubit computational basis states |b>, b \in {0, 1} is considered, see Fig. 1. Our algorithm relies on an extended arithmetic toolbox associated with certain composite unitaries. These realize specific arithmetic functionalities, see Fig. 2. One of these unitaries coherently performs a form of modular exponentiation: It computes x \mapsto f_{a,N,m}(x) for a function f_{a,N,m} such that

f_{a,N,m}(x) \approx a^x \pmod N for all x \in {0, ..., 2^m-1},

(with a, x \in Z_N). Correspondingly, we refer to f_{a,N,m} as a pseudomodular power. (In our algorithm, we set m to be proportional to n, with a constant to be fixed later, see the Supplementary Table 1).

With these preparations, we can complete the description of our algorithm. Its quantum subroutine is given by the circuit Q_{a,N} depicted in Fig. 3, but with the approximate initial GKP states |GKP_{\kappa_A, \Delta_A}>, |GKP_{\kappa_B, \Delta_B}> replaced by the output states of the preparation procedure PG_{\kappa_A, \Delta_A} and PG_{\kappa_B, \Delta_B} (for suitably chosen parameters \kappa_A, \Delta_A, \kappa_B, \Delta_B), respectively. We note that for our choice of parameters (see Supplementary Table 1), both the circuit Q_{a,N} and the preparation procedure PG_{\kappa, \Delta} use operations (i)–(iv). Our quantum subroutine applies a sequence of elementary operations and derived unitaries (see Figs. 1, 2) to the input states and produces a sample w \in R obtained by performing a P-quadrature measurement on the first mode. The shaded subcircuit approximately computes a pseudomodular power. To provide intuition, we will first discuss the effect of the circuit when this subcircuit is replaced by an ideal unitary U^{ideal}_{a,N} computing the real power, see Fig. 4b.

Assume that we run the circuit Q_{a,N} with initial GKP states |GKP_{\kappa_A, \Delta_A}>, |GKP_{\kappa_B, \Delta_B}>. The output is a sample w \in R obtained by performing a P-quadrature measurement on the first mode. The output is processed by an efficient, i.e., polynomial-time classical algorithm, yielding a factor of N with a substantial probability. We have the following:

Lemma 1. Suppose N is an n-bit number. There is a polynomial-time classical algorithm which—given a uniformly chosen element a \in Z^*_N and a single sample from the output distribution of the circuit Q_{a,N} (see Fig. 3)—produces a factor of N with probability at least \Omega(1/log n).

Furthermore, replacing the initial approximate GKP states with the states prepared by the preparation protocol PG_{\kappa, \Delta} leads to a statement comparable to Lemma 1. By repetition with a randomly chosen a \in Z^*_N, we obtain the following by a suitable choice of parameters (see Supplementary Table 1):

Theorem 1. (Efficient quantum algorithm for factoring) There is a polynomial-time algorithm which, given an n-bit integer N,
(I) Repeatedly uses a quantum circuit on three oscillators and one qubit consisting of O(n^2) elementary operations (i)–(iv), and
(II) produces a factor of N with constant probability.

(The success probability can be amplified by repetition or other techniques as in ref. 10).

Our factoring algorithm is the result of translating Shor’s algorithm 10 to CV systems, with specific modifications exploiting their potential. These modifications mean that our construction—although formally quite similar to Shor’s algorithm—is not simply obtained by embedding in a finite-dimensional system. Instead, our approach uses a different algebraic structure: We use an approximate GKP state as a proxy for a uniform superposition over all integers instead of a uniform superposition over all n-bit integers as in Shor’s algorithm. To our knowledge, such an algorithmic use of approximate GKP states is new. Instead of realizing modular arithmetic by gates acting on finite-dimensional systems, our gates natively perform real arithmetic. To realize modular arithmetic, we exploit the (approximate) stabilization property of (approximate) GKP states under suitable (discrete) displacements, a property that underlies their relevance for quantum error correction. Finally, our algorithm averages the Fourier circuit. With these alternative choices, we can show that the physical operations (i)–(iv) (together with an efficient classical computation) are sufficient to address the factoring problem. The difference between our approach and Shor’s algorithm is further expressed in the different complexities: the quantum subroutine of our algorithm has circuit size O(n^2), whereas that of Shor’s algorithm has size O(n^2 log n), when using the best currently known classical algorithm for multiplication with time complexity O(n log n) of ref. 19.

Key ideas
To motivate our construction, recall the basic ingredients of Shor’s algorithm 10, which relies on modular arithmetic and the Fourier transform over Z_q. It builds on the (randomized) reduction 20 of the problem of finding a prime factor of an (odd) integer N to the problem of finding the period r of the function f_{a,N}(x) = a^x mod N, where a \in Z^*_N. (The period r of f_{a,N} can be used to compute a factor of N whenever r is even and x^{r/2} \neq -1 mod N. For a uniformly random integer a \in Z^*_N, the necessary conditions on the period r of f_{a,N} hold in circuit Q_{a,N} except with probability 2^{1-k}, where k is the number of distinct prime factors of N, a bound derived from the Chinese remainder theorem.)

Given a pair (a, N), Shor’s algorithm applies an efficient classical post-processing algorithm to a sample c produced by a (polynomial-size) quantum circuit Q^{Shor}_{a,N}. This gives the period r of the function f_{a,N} with probability at least \Omega(1/log log r), resulting in a polynomial-time factorizational algorithm by repeated application.

A high-level description of Shor’s circuit Q^{Shor}_{a,N} is given in Fig. 4a. It uses a binary encoding of (log q)-bit integers into log q qubits, where q is the smallest power of 2 such that N^2 < q. The circuit starts with the first register in the uniform superposition 1/\sqrt{q} \sum_{x=0}^{q-1} |x> over all integers x \in {0, ..., q-1} = Z_q, coherently computes the function f_{a,N} into a second register using a modular exponentiation unitary U_{Z_N,a} acting as

U_{Z_N,a} (|x> \otimes |y>) = |x> \otimes |y + (a^x mod N)>,

applies the (discrete) Fourier transform FT_{Z_q} on L^2(Z_q) and finally measures the first register in the computational basis giving an outcome c \in {0, ..., q-1}. Shor shows that the output distribution on the outcome c is an integer multiple of q/r with high probability. This property enables the extraction of the period r (The classical post-processing algorithm proceeds as follows: With the continued fraction expansion of c/q, the number c/q is rounded to the nearest fraction of the form r'/r, where r is the period. The value of r is then verified by checking if a^r \equiv 1 mod N).

Here we argue that—in place of the circuit Q^{Shor}_{a,N}—the idealized hybrid circuit Q^{ideal}_{a,N} given in Fig. 4b can be used, assuming that the classical post-processing procedure is appropriately modified. We note that the circuit Q^{ideal}_{a,N} involves non-normalizable GKP states, i.e., the formal uniform superposition

|GKP> \propto \sum_{x \in Z} |x> : (1)

The circuit Q^{ideal}_{a,N} is thus not physical, but it nevertheless illustrates the key ideas underlying our physical circuit Q_{a,N} in Fig. 3. Let us highlight how it differs from Shor’s circuit Q^{Shor}_{a,N}.

First, our algorithm relies on real instead of modular arithmetic. Clearly, the expression (1) is a natural analog of the uniform superposition of basis states used in Shor’s circuit Q^{Shor}_{a,N}. The hybrid circuit Q^{ideal}_{a,N} also uses a CV-analog of the modular exponentiation unitary U_{Z_N,a}. Concretely, consider the unitary U^{ideal}_{R,a,N} which acts on pairs of position-eigenstates |x>, |y> as

U^{ideal}_{R,a,N} (|x> \otimes |y>) = |x> \otimes |y + a^x> where a^x := (a^x mod N) if x \geq 0.

Importantly, the exponentiation in the definition of a^x is not taken modulo N, but is to be understood over the non-negative reals. Integer values belonging to Z_N are only obtained subsequently by means of a modular measurement.

As discussed further in the “Discussion” section, our algorithm produces states whose energy scales extensively in N (the number being factored). This is a natural consequence of an embedding of an exponentially large Hilbert space into a system of three oscillators and one qubit.

Indeed, homodyne P-quadrature measurements (natively available in typical quantum-optical systems) are equivalent to a Fourier transform FT_R on L^2(R) followed by a homodyne Q-quadrature measurement. As such, the circuit Q^{ideal}_{a,N} simply, by applying a GKP state |GKP_{\kappa_B, \Delta_B}> with parameters \kappa_B = \Delta_B = 2^{-\Theta(n)} and \kappa_A = \Delta_A = 2^{-\Theta(n^2)}, respectively. The latter can be produced (approximately) by the protocol PG_{\kappa, \Delta}. The realization by O(n^2) elementary operations (see Fig. 2) can be realized with O(n^2) elementary operations. The circuit Q_{a,N} is the difference between Shor’s circuit Q^{Shor}_{a,N} and the circuit Q_{a,N} is that the latter uses the position of the third mode z=0. That is, we have

|GKP>_{M_N} \propto \sum_{y \in Z} |y \cdot N> in the third mode. This results in a uniform superposition of N. This superposition U_{a,N,m} (|x> \otimes |y>) \otimes |0> \otimes |0> = |x> \otimes |y + f_{a,N,m}(x)> \otimes |0> \otimes |0>,

(Here the qubit is in the state |0>.) The unitary U_{a,N,m} takes the role of U^{ideal}_{R,a,N}(a) in the idealized circuit Q^{ideal}_{a,N} (see Fig. 4b). To ensure that the position of the first mode has most of its support on the set {0, ..., 2^m-1}, the circuit Q_{a,N} involves the unitary e^{-iRP} which shifts the Q_{a,N} is appropriately extracted by GKP-codes 15 see Fig. 5. Our circuit construction of the initial state |GKP_{\kappa_A, \Delta_A}> in the elementary operations is given in the Supplementary Note. We also show this decomposition has the claimed complexity.

The use of physically realizable (approximate) GKP states allows for approximate function evaluation by unitaries on L^2(R) \otimes C^2. This analysis, given in the Supplementary Note, provides detailed estimates on the correctness of the algorithm as a function of the squeezing parameters. Specifically, we have to consider non-integer inputs, i.e., when positions x \in R \setminus Z are involved. By continuity arguments and using the definition of approximate GKP states, we argue that the considered unitaries on inputs supported sufficiently close to the set of integers approximately implement a rounded version of function evaluation. Applied to the circuit Q_{a,N}, this analysis shows that the associated output distribution on R still has the property that the samples can be post-processed to find the period r with a significant probability.

Methods

Peer review rounds
[{"round": 1, "reviewer_comments": {"reviewer_1": "This work proposes a new approach to the construction of quantum algorithms which is more closely connected to the underlying physical hardware and the operations available with this hardware. The authors apply this concept in detail to a variant of a factoring algorithm reminiscent of Shor’s algorithm, but with significant modifications based on the above concept. Unlike for the original Shor algorithm, where both the number of input qubits and the number of gate operations grow with the size of the number to be factored, the authors show that a constant number of initial quantum states – three quantum oscillators and one qubit – suffice, and that a polynomial increase of the number of elementary gate operations alone works in principle.\n\nThe obvious reason for this is that even a single, infinite-dimensional oscillator can carry and process a lot of information, whereas the encoding of the relevant large numbers in Shor’s original scheme requires enough qubits. Less obvious and conceptually even more interesting is how to encode those numbers into the oscillators and how to process them in a suitable way using physically available interactions as provided by common quantum hardware platforms. For this purpose, the authors propose to use Gottesman-Kitaev-Preskill (GKP) oscillator states which are represented by lattices in phase space, and which are most commonly (and originally) associated with GKP qubits, i.e., two-dimensional subspaces of the oscillator space (“encoding a qubit in an oscillator”). GKP qubits exhibit remarkable properties with regards to quantum error correction, fault tolerance, and universality, and these properties motivated their original proposal and much of the subsequent, more recent work related with them. Logical GKP qubits allow to correct small displacement errors into which any physical oscillator error can be decomposed, and they permit efficient deterministic entangling operations which are linear in the mode operators.\n\nDistinct from this, the authors of the present work make use of GKP states to directly encode and process integers through the different peaks in phase space. By physically implementing real arithmetic on GKP states, multiplying and adding numbers by squeezing and displacing the oscillator modes, respectively, the algorithm is directly executed on the physical level. An extra, physical control qubit adds a discrete element (besides the discrete GKP-peaks’ integers) and allows to decide in a “hybrid” qubit-oscillator gate whether, for instance, a multiplication should take place or not. The corresponding qubit-oscillator gates are physically available in platforms that include Jaynes-Cummings-type interactions such as solid-state circuit-QED or atomic cavity-QED.\n\nThis work is a significant contribution to the field of quantum computing. It presents a new, promising concept for an important, prominent application of quantum computing and explicitly works it out in detail and with mathematical rigor. Unlike some other schemes related with “quantum supremacy”, the current scheme is for solving a problem of practical interest. Elements of the proposal have been known and used before, such as hybrid qubit-oscillator gates and GKP states (for both of which universality proofs exist) but combining them in this context and for this type of application is a new idea. The significance of this idea is that it appears to greatly reduce the necessary resources required in a quantum algorithm.\n\nThe paper is very well written. The structure is clear and concise, presenting the most important steps and elements in the main text, and the technical details in the appendix. The detailed figures in the main text further help to illustrate the overall concept. The authors explain their scheme in a “modular way”, and for some of the modules (such as unitary blocks), they first discuss the ideal circuits with unphysical GKP states and as a second step the real circuits with physical states. The treatment of the circuits with physical states is presented in detail in the appendix. This proposal is still a “proof-of-principle proposal” (Conclusions). To exploit the oscillator Hilbert space, the GKP “squeezing” grows with the number to be factored, corresponding to an increase of the average excitation number of the oscillator states. Such high-quality GKP states are not easy to build in any platform. In addition, there is no analysis of fault tolerance (which may be naturally embedded via GKP error correction). These subtleties are openly discussed in the Conclusions section. Therefore, based on the discussion above, I recommend this paper for publication in Nature Communications. There are only a few comments and suggestions that may help to improve the manuscript, which are listed below.\n\n-Terminology: the term boson and bosonic code/state is sometimes used in a slightly misleading way, line 37: “…the underlying physical system (3 bosons and 1 qubit) fixed…”. It’s better to strictly stick to the terminology of the paper title with “3 oscillators and 1 qubit”. Each oscillator in a sufficiently squeezed GKP state will carry many bosons. (What also works is “3 bosonic states/modes and 1 qubit”.)\n-Notation: N is the given integer to be factored, n is the number of bits to represent N; in line 67, the binary representation of the integer x uses a little m (0…2^m -1) in the definition of the pseudomodular power function. Is a new parameter m really needed here? Could we just use n again? Moreover, in line 75, it is again referred to an n in “O(n^2) elementary operations”.\n-Success Probability: in line 57 and in line 92 of Theorem 1, a “constant probability” is mentioned for finding a factor of N. Can we say something about the size of this constant probability (it may be mentioned in the appendix, but it may also be good to say something about this in the main text).\n-Caption of Fig.1: “The two-mode bosonic addition gate… can be decomposed into constantly many beam splitters and single-mode squeezing unitaries [3].” It is well-known from the fields of continuous-variable quantum computing and quantum optics that this gate, also referred to as a CV CSUM gate, can be, like any two-mode squeezing gate, decomposed into a beam splitter, two single-mode squeezers, and another beam splitter (“Bloch-Messiah reduction”). This could simply be stated here, possibly including relevant citations (generally, throughout the paper, there is a little bit of a lack of citations of works related with continuous-variable quantum computing and optics; many of these other works originated from the optics/photonics community, but nonetheless, many of these results directly apply here as well; the primary citation used, the more recent Ref.[3], is already adapted to the hybrid qubit-oscillator setting, but the pure oscillator gates have been introduced and used to a great extent already before in the context of CV QC; there are also earlier “hybrid qubit-oscillator papers”, but they may be cited in Ref.[3]).", "reviewer_2": "This manuscript presents a quantum algorithm for factoring, expressed as a quantum circuit involving an elementary set of operations involving 3 CV systems (oscillators) and a qubit. This is related to, but not identical to, Shor’s quantum algorithm for factoring that is expressed in terms of an elementary set of operations on n qubits. This new algorithm provides an alternative way of expressing the resources required to factor numbers using a quantum computer. Because of the keen interest in Shor’s algorithm and understanding the resources it requires, this result is noteworthy, as alternative perspectives on the required resources may provide insight into these resource requirements and may lead to some innovation in reducing these resources, although the latter is not explored here.\n\nThis result should be of interest to a range of quantum computing researchers, including both those focused on developing and understanding quantum algorithms, and also those (including experimentalists) considering resource-efficient ways of running quantum algorithms. The results in this manuscript are framed using CV quantum operations and GKP states, which are very intensely-studied at the moment, including considerable experimental investigation. Certainly, researchers in CV quantum systems using GKP encodings will be interested in re-casting various quantum algorithms into more ‘natural’ native operations and exploring if this leads to some efficiency in resources, or even just a different approach to viewing an algorithm or protocol. There is considerable existing research in this broad area and the authors have done a good job at citing the relevant literature.\n\nI am quite confident in the validity of the claims here. There is considerable technical detail given in the appendices, and the authors have summarized the key elements in the main part of the manuscript. I do not see any reason to question the technical correctness of these results, and the work should definitively be published in some form.\n\nThis will be an interesting new result for a range of researchers. The remaining question is whether the result is of sufficient importance and significance to merit publication in Nature Communications, based on the journal’s selection criteria. Here, I must unfortunately question whether this result will have lasting significance or a large impact. As well summarized by the authors in the conclusions, the paper does not attempt to present any analysis of the resources required, or to compare these resources (in any way) to those needed for Shor’s algorithm. They do not touch on the issue of fault tolerance. So the reader is really left wondering, ‘what does this mean?’ Have we understood something new about the tradeoff in moving from the standard qubit-based approach to the CV approach? Have we gained any understanding on how the range of CV/GKP experimental platforms currently being explored might be able to make use of the results here? I feel that the authors have presented a novel theoretical idea, but it does not yet sit clearly in the broader field of research and there is little here to help guide the reader or give future directions to understand where it sits or might sit.\n\nThe manuscript is likely to be more suited for a specialist journal, where researchers in quantum algorithms might access this result over time and start to address some of these questions.", "reviewer_3": "While the standard model of quantum computation is formulated in terms of discrete variables (DV) in finite-dimensional Hilbert spaces, many degrees of freedom, such as bosons, are continuous variables (CV) described by infinite-dimensional Hilbert spaces. Understanding the power of these degrees of freedom is an important research direction. Due to infinite dimensions, one expects more computational capabilities from such devices. At the same time, due to rapid energy accumulations, controlling CV degrees of freedom is a tedious task, particularly when superquadratic Hamiltonians are considered. An intermediate paradigm of computation is to couple CV and DV degrees of freedom. This paper considers this framework. They use qubit-controlled (up to quadratic) CV operations. Such a gate set includes a quantum Fourier transform over the continuous domain (by measuring a state function that is specified in the position basis in the momentum basis). They furthermore use the well-known GKP states used for quantum error correction as a resource. The main result of this paper is factoring using only three CV degrees of freedom (aka oscillators) and one qubit. The algorithm is very similar to Shor's original algorithm, implemented using native CV operations. This is a neat result. It is furthermore well-written. And I recommend acceptance if there is availability.\n\nThe main comment I have for the authors is that, even though the model you use has polynomial \"time\" complexity and a constant number of modes, it still uses exponential energy. I believe you need to emphasize this early on. You do explain that this is not a practical problem, but emphasizing energy as a resource would be nice as well.\n\nOne question I have is: What prevents you from achieving universal quantum computation with this model? You may be aware that follow-up work on Chabaud et al. shows that other CV gate sets using exp energy can solve arbitrary NP problems. Also, you do reference the Shamir result, which uses arithmetic operations in a unit step of time. I believe if we think deeply about that result, the main assumption they are using is also about energy consumption in unit time/space. So, in that regard, it is not immediately clear if a bosonic algorithm like the one you used if fundamentally different. For example, here is a question to think about: Can we implement factoring using a classical CV model of computation?\n\nThe result is neat. With the time budget I had I could not verify every detail but they do seem reasonable. What I am struggling to understand is why the supplementary material is very long. After going over the warm-up example, I was relatively convinced that the result should hold for more energy-restricted resources. I recommend offering some insight into the main complications in making everything rigorous. As far as I understand, since the gate set you are working on is Gaussian-coupled to DV degrees of freedom, there are not many tedious domain issues.\n\nThe statement of Proposition 1 is a bit unclear to me. What do you mean by suitable in item ii?"}, "author_response": "We would like to thank the referees for the careful examination of our manuscript and the\nhelpful comments and suggestions in particular. We have now revised the manuscript\ntaking into account the referees’ feedback. Please find below our detailed\npoint-by-point responses to the referees’ comments along with a summary of the changes\nmade.\nReviewer #1 (Remarks to the Author):\nThis work proposes a new approach to the construction of quantum algorithms which is\nmore closely connected to the underlying physical hardware and the operations available with\nthis hardware. The authors apply this concept in detail to a variant of a factoring algorithm\nreminiscent of Shor’s algorithm, but with significant modifications based on the above concept.\nUnlike for the original Shor algorithm, where both the number of input qubits and the number\nof gate operations grow with the size of the number to be factored, the authors show that a\nconstant number of initial quantum states – three quantum oscillators and one qubit – suffice,\nand that a polynomial increase of the number of elementary gate operations alone works in\nprinciple.\nResponse: We believe this accurately summarizes our contribution.\nThe obvious reason for this is that even a single, infinite-dimensional oscillator can carry\nand process a lot of information, whereas the encoding of the relevant large numbers in\nShor’s original scheme requires enough qubits. Less obvious and conceptually even more\ninteresting is how to encode those numbers into the oscillators and how to process them\nin a suitable way using physically available interactions as provided by common quantum\nhardware platforms. For this purpose, the authors propose to use Gottesman-Kitaev-Preskill\n(GKP) oscillator states which are represented by lattices in phase space, and which are most\ncommonly (and originally) associated with GKP qubits, i.e., two-dimensional subspaces of\nthe oscillator space (“encoding a qubit in an oscillator”). GKP qubits exhibit remarkable\nproperties with regards to quantum error correction, fault tolerance, and universality, and\nthese properties motivated their original proposal and much of the subsequent, more recent\nwork related with them. Logical GKP qubits allow to correct small displacement errors into\nwhich any physical oscillator error can be decomposed, and they permit efficient deterministic\nentangling operations which are linear in the mode operators.\nResponse: We agree with the need to propose concrete schemes for CV systems: Di-\nmensional considerations alone are not sufficient in order to claim that infinite-dimensional\nsystems are useful for quantum information processing.\nDistinct from this, the authors of the present work make use of GKP states to directly\nencode and process integers through the different peaks in phase space. By physically\nimplementing real arithmetic on GKP states, multiplying and adding numbers by squeezing\nand displacing the oscillator modes, respectively, the algorithm is directly executed on the\nphysical level. An extra, physical control qubit adds a discrete element (besides the discrete\nGKP-peaks’ integers) and allows to decide in a “hybrid” qubit-oscillator gate whether, for\ninstance, a multiplication should take place or not. The corresponding qubit-oscillator gates\nare physically available in platforms that include Jaynes-Cummings-type interactions such as\nsolid-state circuit-QED or atomic cavity-QED.\nResponse: Our proposal to use GKP states in an algorithmic context is indeed new to\nthe best of our knowledge. We also think that the physical realizability of the associated\noperations in widely available systems is a distinctive feature of our model.\nnew, promising concept for an important, prominent application of quantum computing and\nexplicitly works it out in detail and with mathematical rigor. Unlike some other schemes\nrelated with “quantum supremacy”, the current scheme is for solving a problem of practical\ninterest. Elements of the proposal have been known and used before, such as hybrid qubit-\noscillator gates and GKP states (for both of which universality proofs exist) but combining\nthem in this context and for this type of application is a new idea. The significance of this idea\nis that it appears to greatly reduce the necessary resources required in a quantum algorithm.\nResponse: We thank the reviewer for this positive assessment. Of course, whether or not\nfactoring is a problem of practical interest may be questioned, but we agree that finding\ncomputational advantages with potential applications is a central goal for our field. We\nhope our work inspires novel approaches to quantum algorithms design.\nThe paper is very well written. The structure is clear and concise, presenting the most\nimportant steps and elements in the main text, and the technical details in the appendix. The\ndetailed figures in the main text further help to illustrate the overall concept. The authors\nexplain their scheme in a “modular way”, and for some of the modules (such as unitary\nblocks), they first discuss the ideal circuits with unphysical GKP states and as a second step\nthe real circuits with physical states. The treatment of the circuits with physical states is\npresented in detail in the appendix. This proposal is still a “proof-of-principle proposal”\n(Conclusions). To exploit the oscillator Hilbert space, the GKP “squeezing” grows with the\nnumber to be factored, corresponding to an increase of the average excitation number of\nthe oscillator states. Such high-quality GKP states are not easy to build in any platform.\nIn addition, there is no analysis of fault tolerance (which may be naturally embedded via\nGKP error correction). These subtleties are openly discussed in the Conclusions section.\nTherefore, based on the discussion above, I recommend this paper for publication in Nature\nCommunications. There are only a few comments and suggestions that may help to improve\nthe manuscript, which are listed below.\nResponse: We thank the referee for their evaluation and these positive comments. We\nfully agree with the statement that many key problems remain, including, in particular, the\nquestion of fault-tolerance and the required amount of squeezing and associated scalability\nissues. As we emphasize in the manuscript, our proposal is a proof of principle. It would be\nexciting to see corresponding small-scale proof of principle experiments.\nReviewer’s comment: -Terminology: the term boson and bosonic code/state is sometimes\nused in a slightly misleading way, line 37: “...the underlying physical system (3 bosons and\n1 qubit) fixed...”. It’s better to strictly stick to the terminology of the paper title with “3\noscillators and 1 qubit”. Each oscillator in a sufficiently squeezed GKP state will carry many\nbosons. (What also works is “3 bosonic states/modes and 1 qubit”.)\nResponse: We thank the referee for this suggestion. As they correctly point out, the term\nboson(s) is often used to refer to occupation numbers, and this is not the intended meaning\nhere. Correspondingly, we have adopted this change.\n“the underlying physical system (3 bosons and 1 qubit) fixed”\nto:\n“the underlying physical system (3 oscillators and 1 qubit) fixed”\nand also:\n“By associating a single physical information carrier (a boson) to each individual\nqubit, this philosophy emphasizes modularity”\nto:\n“By associating a single physical information carrier (an oscillator) to each indi-\nvidual qubit, this philosophy emphasizes modularity”\nReviewer’s comment: -Notation: N is the given integer to be factored, n is the number\nof bits to represent N; in line 67, the binary representation of the integer x uses a little m\n(0,...,2m -1) in the definition of the pseudomodular power function. Is a new parameter m\nreally needed here? Could we just use n again? Moreover, in line 75, it is again referred to\nan n in “O(n2) elementary operations”.\nResponse: Inouranalysis,wesetmequaltom = 17n(seetheSupplementaryTable1). The\nfact that this parameter needs to be different from n is similar to the reason the first register\nin Shor’s algorithm has size at least 2n and not n: This is required to obtain a sufficient\nprecision in the representation of (rational) numbers in the continued fraction algorithm.\nIn other words, m determines the precision. In our case, our concrete choice of m = 17n\nensures that our realization of pseudomodular exponentiation is sufficiently accurate even in\nthe non-ideal case when using approximate GKP states.\nFor this reason, we prefer to keep referring to this parameter by separate variable (instead\nof e.g., replacing m by 17n throughout).\nIn Line 75, the parameter n is the number of bits used to represent the input of algorithm\n(i.e., number N to be factored). In other words, it represents the length of the input of the\ncomputational problem, and is therefore the natural quantity to measure complexity in.\nChanges: We included more precise reference for the parameters of the approximate GKP\nstates used in our algorithm.\nSpecifically, we have additionally included the following explanation around Line 67:\n“ (In our algorithm, we set m to be proportional to n, with a constant to be fixed\nlater, see the Supplementary Table 1).”\nand we made the following change around line 75:\n“We note that for our choice of parameters (see the supplementary information)\n...”\n4\nwas changed to\n“We note that for our choice of parameters (see Supplementary Table 1) ...”\nReviewer’s comment: -Success Probability: in line 57 and in line 92 of Theorem 1, a\n“constant probability” is mentioned for finding a factor of N. Can we say something about\nthe size of this constant probability (it may be mentioned in the appendix, but it may also be\ngood to say something about this in the main text).\nResponse: Bothprobabilitiescanbeamplifiedwithoutchangeincomplexitytoanarbitrary\nconstant close to 1 by repetition. The ultimate success probability then depends on the\nnumber rounds of repetition in Theorem 1 (i).\nChanges: We included the following: Line 57, we added:\n“(which can be amplified by repetition to an arbitrary constant without change\nin complexity)”.\nLine 92: we added\n“(The success probability can be amplified by repetition or other techniques as\nin [Shor].)”\nright after the Theorem 1.\nReviewer’s comment: -Caption of Fig.1: “The two-mode bosonic addition gate... can be\ndecomposed into constantly many beam splitters and single-mode squeezing unitaries [3].” It\nis well-known from the fields of continuous-variable quantum computing and quantum optics\nthat this gate, also referred to as a CV CSUM gate, can be, like any two-mode squeezing\ngate, decomposed into a beam splitter, two single-mode squeezers, and another beam splitter\n(“Bloch-Messiah reduction”). This could simply be stated here, possibly including relevant\ncitations (generally, throughout the paper, there is a little bit of a lack of citations of works\nrelated with continuous-variable quantum computing and optics; many of these other works\noriginated from the optics/photonics community, but nonetheless, many of these results di-\nrectly apply here as well; the primary citation used, the more recent Ref.[3], is already adapted\nto the hybrid qubit-oscillator setting, but the pure oscillator gates have been introduced and\nused to a great extent already before in the context of CV QC; there are also earlier “hybrid\nqubit-oscillator papers”, but they may be cited in Ref.[3]).\nResponse: We agree that including additional references discussing standard quantum\nlinear optics and its relation to quantum computing make sense.\nChanges: We have included a reference for the Bloch-Messiah reduction in the caption of\nFigure 1.\nAdditionally, we have included the following new references:\n1. Chuang and Yamamoto. Simple quantum computer. Phys. Rev. A, 52:3489–3496, Nov\n1995.\n5\n2. Lloyd and Braunstein. Quantum computation over continuous variables. Phys. Rev.\nLett., 82:1784–1787, Feb 1999.\n3. Knill, Laflamme, and Milburn. A scheme for efficient quantum computation with linear\noptics. Nature, 409(6816):46–52, Jan 2001.\n4. Kok, Munro, Nemoto, Ralph, Dowling, and Milburn. Linear optical quantum computing\nwith photonic qubits. Rev. Mod. Phys., 79:135–174, Jan 2007.\n5. Cerf,Adami,andKwiat. Opticalsimulationofquantumlogic. Phys. Rev. A,57:R1477–R1480,\nMar 1998.\nIf the reviewer has additional relevant suggestions we kindly ask them to let us know.\nThis manuscript presents a quantum algorithm for factoring, expressed as a quantum circuit\ninvolving an elementary set of operations involving 3 CV systems (oscillators) and a qubit.\nThis is related to, but not identical to, Shor’s quantum algorithm for factoring that is ex-\npressed in terms of an elementary set of operations on n qubits. This new algorithm provides\nan alternative way of expressing the resources required to factor numbers using a quantum\ncomputer. Because of the keen interest in Shor’s algorithm and understanding the resources\nit requires, this result is noteworthy, as alternative perspectives on the required resources may\nprovide insight into these resource requirements and may lead to some innovation in reducing\nthese resources, although the latter is not explored here.\nResponse: Astherefereecorrectlyemphasizes, ouralgorithmisindeeddifferentfromShor’s\nalgorithm, or a CV embedding thereof. We share the referee’s view that exploring such alter-\nnative approaches may lead to new and potentially more easily realizable implementations.\nThis result should be of interest to a range of quantum computing researchers, includ-\ning both those focused on developing and understanding quantum algorithms, and also those\n(including experimentalists) considering resource-efficient ways of running quantum algo-\nrithms. The results in this manuscript are framed using CV quantum operations and GKP\nstates, which are very intensely-studied at the moment, including considerable experimental\ninvestigation. Certainly, researchers in CV quantum systems using GKP encodings will be\ninterested in re-casting various quantum algorithms into more ‘natural’ native operations and\nexploring if this leads to some efficiency in resources, or even just a different approach to\nviewing an algorithm or protocol. There is considerable existing research in this broad area\nand the authors have done a good job at citing the relevant literature.\nResponse: We thank the referee for their assessment concerning the timeliness of our\ncontribution. This is a rapidly evolving subfield of quantum information processing, and it\nwould be great to see more algorithmic applications of improved experimental capabilities.\nI am quite confident in the validity of the claims here. There is considerable technical\ndetail given in the appendices, and the authors have summarized the key elements in the\nmain part of the manuscript. I do not see any reason to question the technical correctness\nof these results, and the work should definitively be published in some form.\nThis will be an interesting new result for a range of researchers. The remaining question\nis whether the result is of sufficient importance and significance to merit publication in Na-\nture Communications, based on the journal’s selection criteria. Here, I must unfortunately\nquestion whether this result will have lasting significance or a large impact. As well summa-\nrized by the authors in the conclusions, the paper does not attempt to present any analysis of\nthe resources required, or to compare these resources (in any way) to those needed for Shor’s\nalgorithm. They do not touch on the issue of fault tolerance. So the reader is really left\nwondering, ‘what does this mean?’ Have we understood something new about the tradeoff in\nmoving from the standard qubit-based approach to the CV approach? Have we gained any\nunderstanding on how the range of CV/GKP experimental platforms currently being explored\nmight be able to make use of the results here? I feel that the authors have presented a novel\ntheoretical idea, but it does not yet sit clearly in the broader field of research and there is\n7\nlittle here to help guide the reader or give future directions to understand where it sits or\nmight sit.\nResponse: The referee raises important open questions. In particular, the issue of fault-\ntolerance is highly relevant and demands further attention. However, it is also highly non-\ntrivial. We hope our concrete proposal can serve as a paradigmatic example of a protocol\nfor which CV/DV-fault-tolerance tools can be developed.\nIn terms of resources, our estimates give detailed bounds on the circuit complexity, show-\ning that our algorithm runs in polynomial time (and with polynomial circuit size), similar to\nShor’s algorithm. A more direct comparison is challenging because the underlying physical\nsetup is very different. We note that the connection between qubit-based computation and\nCV/DV-circuits has been analyzed further with respect to the amount of energy required,\nsee [Brenner, Dias, Koenig. Trading modes against energy. arXiv:2509.18854]\nThe manuscript is likely to be more suited for a specialist journal, where researchers in\nquantum algorithms might access this result over time and start to address some of these\nquestions.\nResponse: We thank the reviewer for his report. We strongly believe that our work will\ninspire further research in hardware-inspired quantum computing, hybrid qubit-oscillator\narchitectures, and fault-tolerant protocols for their use. We believe the visibility gained\nfrom exposure to the broad readership of Nature Communications will accelerate the uptake\nof the interdisciplinary questions we raise.\nWhile the standard model of quantum computation is formulated in terms of discrete vari-\nables (DV) in finite-dimensional Hilbert spaces, many degrees of freedom, such as bosons, are\ncontinuous variables (CV) described by infinite-dimensional Hilbert spaces. Understanding\nthe power of these degrees of freedom is an important research direction. Due to infinite\ndimensions, one expects more computational capabilities from such devices. At the same\ntime, due to rapid energy accumulations, controlling CV degrees of freedom is a tedious task,\nparticularly when superquadratic Hamiltonians are considered. An intermediate paradigm of\ncomputation is to couple CV and DV degrees of freedom. This paper considers this frame-\nwork. They use qubit-controlled (up to quadratic) CV operations. Such a gate set includes\na quantum Fourier transform over the continuous domain (by measuring a state function\nthat is specified in the position basis in the momentum basis). They furthermore use the\nwell-known GKP states used for quantum error correction as a resource. The main result\nof this paper is factoring using only three CV degrees of freedom (aka oscillators) and one\nqubit. The algorithm is very similar to Shor’s original algorithm, implemented using native\nCV operations. This is a neat result. It is furthermore well-written. And I recommend\nacceptance if there is availability.\nResponse: We thank the referee for their evaluation and these positive comments, as well\nas their accurate summary.\nWe believe the CV/DV-model is of independent interest because it models various phys-\nical systems of experimental relevance. We do not see our work as an intermediate step in\ntransitioning to the study of superquadratic Hamiltonians, but rather a different computa-\ntional model. It will be interesting to see connections.\nReviewer’s comment: The main comment I have for the authors is that, even though\nthe model you use has polynomial ”time” complexity and a constant number of modes, it still\nuses exponential energy. I believe you need to emphasize this early on. You do explain that\nthis is not a practical problem, but emphasizing energy as a resource would be nice as well.\nResponse: We have covered this aspect in detail in our discussion section: In fact, about\nhalf of this section is devoted to the question of energy/squeezing. While we believe this\nprovides an adequate treatment and would prefer not to complicate the presentation of the\nalgorithm and its complexity earlier in manuscript, we are open to concrete suggestions\nbeyond the corresponding changes made, see below.\nChanges: We included the following paragraph right after the statement of the main the-\norem (Theorem 1) and discussion about the differences between our and Shor’s algorithm.\n“As discussed further in the Discussion section, our algorithm produces states\nwhose energy scales extensively in N (the number being factored). This is a\nnatural consequence of an embedding of an exponentially large Hilbert space\ninto a system of three oscillators and one qubit.”\nquantum computation with this model?\nResponse: Universal quantum computation can indeed be achieved with this model, see\nthe work [Brenner, Dias, Koenig. Trading modes against energy. arXiv:2509.18854].\nReviewer’s comment: You may be aware that follow-up work on Chabaud et al. shows\nthat other CV gate sets using exp energy can solve arbitrary NP problems. Also, you do\nreference the Shamir result, which uses arithmetic operations in a unit step of time. I believe\nif we think deeply about that result, the main assumption they are using is also about energy\nconsumption in unit time/space. So, in that regard, it is not immediately clear if a bosonic\nalgorithm like the one you used if fundamentally different. For example, here is a question\nto think about: Can we implement factoring using a classical CV model of computation?\nResponse: The referee raises an intriguing question. In our opinion, however, our result is\nnot directly comparable, neither to the model considered by Chabaud et al., nor the result\nobtained by Shamir, for different reasons.\nThe hybrid CV-DV model we consider has the following properties:\n1. all elementary operations we use are physically motivated and appear in present ex-\nperimental setups, for more details see the review [arXiv:2407.10381]. In particular\nlinear optics operations and preparation of a qubit in the |0⟩ state and Hadamard\ngates are standard. Qubit-controlled displacement and phase space rotations were\nsuccessfully realized, e.g., [Eickbusch et al. Nat. Phys., 18(12):1464–1469 (2022);\nCampagne-Ibarcq et al. Nature, 584:368–372 (2020); Boissonneault et al. Phys. Rev.\nA, 79:013819 (2009)],\n2. the energy can grow at most exponentially with the number of elementary operations.\nIn particular, unlike for certain non-Gaussian operations, see, e.g., [Chabaud et al.\n’25], our circuits cannot produce states with unbounded energy in a constant time.\n3. the complexity (number of elementary operations) is closely related to the (effective)\nsize of a binary representation of any number used during the course of computation\n(e.g. encoded in the position basis).\nThese properties are not shared with the computational model used in Chabaud et al. ’25.\nFor the work by Shamir ’79, the differences to our work are equally stark: Shamir works\nin a computational model which is entirely detached from any physical realization. Corre-\nspondingly, notions such as energy are not naturally defined.\nThesecoredifferencessetourmodelapartfromtheonescitedbythereviewer. Webelieve\nthat these profound differences are not fully captured by a discussion of ’energy consumption\nin unit time/space’.\nChanges: We have added the following sentence to the Discussion section.\nIn more recent work, Chabaud et al. [Chabaud et al. ’25] analyze the computa-\ntional power of a CV systems with superquadratic Hamiltonians. We emphasize\n10\nthat their model significantly differs from ours as individual gates can increase\nthe energy by a superlinear amount. Such gates appear challenging to realize\nexperimentally at present.\nLet us also comment on factoring in a classical CV model: Shamir’s result can be cast\nas a factoring of integers embedded in a classical CV system but without a physically mo-\ntivated setup. This distinction is crucial. If one disregards the constraints of a physical\nimplementation, it is trivial to postulate abstract classical models that factor any integer in\nunit time.\nReviewer’s comment: The result is neat. With the time budget I had I could not verify\nevery detail but they do seem reasonable. What I am struggling to understand is why the\nsupplementary material is very long. After going over the warm-up example, I was relatively\nconvinced that the result should hold for more energy-restricted resources. I recommend\noffering some insight into the main complications in making everything rigorous. As far as\nI understand, since the gate set you are working on is Gaussian-coupled to DV degrees of\nfreedom, there are not many tedious domain issues.\nResponse: The complications arise from the following:\n(i) the necessity to decompose the idealized (exponentiation) unitary into elementary op-\nerations we use. We give a decomposition whose complexity is better than what is done\nin Shor’s algorithm, i.e., O(n2) qubit gates vs. O(n2logn) elementary operations.\n(ii) the necessity to use physically meaningful, that is, normalizable states (instead of for-\nmalpositioneigenstates). Themainpointofouranalysisestablishesthatouralgorithm\n(initially designed with formal position eigenstates in mind) still approximately evalu-\nates the desired function.\nBoth giving an efficient decomposition and analyzing the effect of finite squeezing are non-\ntrivial tasks.\nChanges: Wechangedthefollowingin“Acircuitcomposedofphysicaloperations”section:\n“Theuseofphysicallyrealizable(approximate)GKPstates|GKP ⟩and|GKP ⟩\nκA,∆A κB,∆B\nwith (finite) squeezing parameters (κ ,∆ ) and (κ ,∆ ) in the circuit Q ne-\nA A B B a,N\ncessitatesadetailedanalysisoffunctionevaluationbyunitariesonL2(R)⊗3⊗C2.”\nwas changed to\n“We give a decomposition of the unitary U into elementary operations in\na,N,m\nthe Supplementary Note. We also show this decomposition has the claimed\ncomplexity.\nTheuseofphysicallyrealizable(approximate)GKPstates|GKP ⟩and|GKP ⟩\nκA,∆A κB,∆B\nwith (finite) squeezing parameters (κ ,∆ ) and (κ ,∆ ) in the circuit Q ne-\nA A B B a,N\ncessitates a detailed analysis of approximate function evaluation by unitaries\non L2(R)⊗3 ⊗C2. This analysis, given in the Supplementary Note, provides de-\ntailed estimates on the correctness of the algorithm as a function of the squeezing\nparameters.”\nyou mean by suitable in item ii?\nResponse: The notion of suitability is defined before the Proposition. We have added a\ncomment referring to this.\nChanges: We included “(see Definition 2.1)” that defines a “suitable family of probability\ndensity functions”.\nOnce again, we thank all three reviewers for their constructive comments.\n12"}]

Decision letter