PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantum arithmetic with the Quantum Fourier Transform

Lidia Ruiz-Perez, Juan Carlos Garcia-Escartin

arXiv:1411.5949v2quant-ph

TL;DR

Quantum arithmetic needs efficient implementations of modular and related operations. This paper studies QFT adders and multipliers, modifies them for broader arithmetic, and introduces weighted-sum and average circuits. The constructions include compact qubit implementations and programmable weighted sums, with stated gate-complexity bounds and fixed-point requirements for non-integer means.

  • Problem

    Quantum arithmetic requires quantum implementations of modular operations that form building blocks for quantum factoring, while existing proposals use varied adder and multiplier constructions.

  • Method

    The paper studies QFT adders and multipliers, modifies them for non-modular and signed arithmetic, and develops mean, weighted-sum, and programmable inner-product circuits.

  • Results

    QFT adders use O(n^2) gates and multipliers O(n^3) gates for n-bit integers; quantum weighted sums support quantum weights and values with O(Ntqn) gates.

  • Takeaways & Limitations

    Arithmetic means and weighted averages can use the same number of gates as basic QFT addition, enabling programmable weighted-sum calculation without separately computing each weight-value product.

  • Takeaways & Limitations

    Non-integer means require fixed-point encodings and expanded state space, while non-modular weighted sums or signed inputs may require a different ancillary-qudit dimension.

Abstract

from arXiv · show

The Quantum Fourier Transform offers an interesting way to perform arithmetic operations on a quantum computer. We review existing Quantum Fourier Transform adders and multipliers and propose some modifications that extend their capabilities. Among the new circuits, we propose a quantum method to compute the weighted average of a series of inputs in the transform domain.

1 Introduction. Quantum arithmetic

The paper reviews QFT-based quantum arithmetic and extends QFT adders and multipliers to modular, non-modular, signed, weighted-sum, and inner-product operations.

  • 1 Introduction. Quantum arithmetic: QFT adders and multipliers provide an elegant quantum alternative to reversible classical arithmetic constructions.The paper situates these circuits alongside teleportation-, measurement-, and nearest-neighbour-based approaches.
  • 1 Introduction. Quantum arithmetic: The paper studies QFT arithmetic for modular and non-modular operations and introduces a circuit for weighted sums.A controlled version of the weighted-sum circuit can implement inner products.
  • 1 Introduction. Quantum arithmetic: Modified QFT adders compute non-modular additions and signed arithmetic, including subtraction.The paper also describes elementary-gate implementations for qubits.
  • 1 Introduction. Quantum arithmetic: The proposed extensions compute arithmetic means, weighted sums, and multiplication by constants.The weighted-adder construction sums inputs after multiplication by constant weights.
  • 1 Introduction. Quantum arithmetic: Qubit QFT multipliers support programmable weighted adders for arbitrary input integers and weights, including different vector inner products.These circuits are assembled from modified QFT adders and multipliers.

2 The Quantum Fourier Transform and distributed phase encoding

The QFT changes from computational-basis number encoding to distributed phase encoding, enabling arithmetic operators to act on relative phases.

  • 2 The Quantum Fourier Transform and distributed phase encoding: The QFT provides an alternative representation for performing arithmetic operations on a quantum computer.It is defined for a d-dimensional system whose computational basis contains states |0⟩ through |d−1⟩.
  • 2 The Quantum Fourier Transform and distributed phase encoding: The QFT encodes a number x in the relative phases of a uniform superposition over computational-basis states.Each basis state |k⟩ receives a phase proportional to xk.
  • 2 The Quantum Fourier Transform and distributed phase encoding: The transformed state |φ(x)⟩ is defined as QFT|x⟩ and represents x in the phase basis.The QFT can be interpreted as a change of basis.
  • 2 The Quantum Fourier Transform and distributed phase encoding: The direct QFT and inverse QFT move information between the computational basis and phase representation.The inverse transform converts phase encoding back to computational-basis encoding.
  • 2 The Quantum Fourier Transform and distributed phase encoding: This phase encoding is the common basis of existing QFT arithmetic proposals.QFT adders and related arithmetic operators act on the distributed phases.

3 QFT adders

QFT adders encode one operand in phases and use controlled phase shifts to add inputs, with modifications supporting multiple, non-modular, and signed arithmetic.

  • 3 QFT adders: Controlled phase gates add an integer to a target register through its distributed phase encoding.The controlled Pauli Z gate is the basic two-input example.
  • 3 QFT adders: The controlled phase gates generalize from qubits to qudits and can include a divisor factor F for later constructions.These gates correspond to controlled rotation gates with different rotation angles.
  • 3 QFT adders: The basic QFT adder performs addition modulo d by applying QFT, a controlled phase operation, and inverse QFT.The operation maps |x⟩|y⟩ to |x⟩|x + y (mod d)⟩.
  • 3 QFT adders: The adder extends to N inputs and outputs their sum modulo d while retaining the other input registers.An ancillary target register can preserve all inputs while storing the sum.
  • 3 QFT adders: Non-modular addition uses a larger dimension, with d′ = 2d − 1 for two inputs and d′ = Nd − N + 1 for N inputs.The QFT and controlled-phase circuits must be adapted to the enlarged dimension.
  • 3 QFT adders: Signed encoding maps −x to |d − x⟩, allowing the QFT adder to perform signed addition and subtraction.Positive numbers x < d/2 remain encoded as |x⟩.

4 QFT Adder. Qubit implementation

The qubit implementation decomposes Draper’s QFT adder into QFT and controlled rotation gates, enlarging the accumulator to support non-modular sums without extra ancillas.

  • 4 QFT Adder. Qubit implementation: The qubit implementation represents input integers with n qubits and decomposes the adder into elementary conditional phase rotations.The common qubit basis is used for numbers encoded from 0 to 2^n − 1.
  • 4 QFT Adder. Qubit implementation: Draper’s circuit transforms |a⟩ into |φ(a)⟩, applies rotations controlled by the qubits of b, and obtains |φ(a + b)⟩.The b register remains unchanged while the transformed a register receives the sum.
  • 4 QFT Adder. Qubit implementation: Figure 1 depicts the QFT of the state |0⟩|a⟩, with phase-state components corresponding to the transformed register.The figure omits SWAP gates used to reverse output-qubit order.
  • 4 QFT Adder. Qubit implementation: An ancillary leading qubit encodes a in an n + 1-qubit register to avoid overflow and recover the ordinary integer sum.After inverse QFT, the sum is returned to the computational basis.
  • 4 QFT Adder. Qubit implementation: The resulting QFT adder has the minimum size needed to contain the result and requires no additional ancillary qubits.This distinguishes it from some reversible adders based on classical schemes.
  • 4 QFT Adder. Qubit implementation: Figure 2 presents the arithmetic non-modular sum in the transform domain using the controlled-rotation construction.The enlarged register provides space for the non-modular result.

5 Computing the mean with the QFT

The paper modifies a QFT adder to compute the arithmetic mean of encoded integers. Because the mean may be non-integer, fixed-point encoding or phase estimation is needed to recover it accurately.

  • Computing the mean with the QFT: Replacing the adder’s CZ gates with CZN gates produces the desired arithmetic mean of N encoded integers.The construction uses an ancillary |0⟩ qudit.
  • Computing the mean with the QFT: The arithmetic mean remains within 0 to d−1, so it is equivalent to modular addition in that range.This equivalence holds because the mean of values from 0 to d−1 cannot exceed the same range.
  • Computing the mean with the QFT: Non-integer means are not generally returned as integers by inverse-QFT phase-to-computational-basis conversion.The issue arises because the computational basis directly represents integer values.
  • Computing the mean with the QFT: Fixed-point encoding expands the state space to represent fractional means; with log2(Nd) qubits, the general weighted-sum circuit recovers the correct mean.Phase estimation offers an alternative, producing the best possible m-bit phase approximation with probability at least 4/π2 for d = 2^m.

6 Weighted sums and multiplication by a constant

The paper generalizes the QFT adder to compute weighted sums and identifies constant multiplication as a special case. The resulting circuit computes modulo d weighted sums, while non-modular or non-integer cases require additional encoding or estimation changes.

  • Weighted sums: The modified QFT method can compute weighted sums of encoded inputs.The paper then develops a qubit multiplier and programmable weighted adder from related constructions.
  • Weighted sums: The circuit maps encoded inputs to an ancillary register containing a1x1 + a2x2 + . . . + aNxN (mod d).The inputs remain present while the weighted sum is stored in the ancillary output.
  • Weighted sums: Non-modular weighted sums and signed inputs may require a different ancillary dimension, reusing the adder modifications from Section 3.The required dimension depends on the allowed range of the result.
  • Weighted sums: When positive integer weights sum to 1, the total weighted sum is guaranteed to equal the modulo d sum.The arithmetic-mean case has am = 1/N for all m, as described in the paper.
  • Weighted sums: Non-integer weights require either fixed-point state-space expansion or a phase-estimation stage to recover the weighted-sum result.This extends the representation issue identified for arithmetic means.
  • Multiplication by a constant: Multiplication by a constant is a weighted sum implemented using the binary decomposition of the constant.For an n-bit constant b, bx is expressed as a sum of weighted terms involving x.

7 QFT Multiplier

The paper constructs an exact QFT multiplier from consecutive controlled QFT additions, with register sizing and gate choices supporting both ordinary and power-of-two modular multiplication.

  • QFT multiplier: Two n-bit numbers are multiplied by performing n consecutive controlled QFT additions, producing a 2n-qubit register encoding a · b.The circuit is formed from controlled weighted-sum blocks.
  • Controlled additions: The first controlled adder adds a to an ancillary register when the least significant qubit of b is 1.The ancillary register is initialized in the Fourier-transformed zero state.
  • Controlled additions: Successive controlled adders scale the phase addition by powers of two corresponding to higher-order qubits of b.The accumulated state represents b0a + b1 2a + … + bn−1 2^(n−1)a.
  • Gate construction: The product is obtained by selecting conditional phase rotations that implement each controlled QFT adder block.The rotation gates are chosen using the input bits of a and the control bit bj.
  • Register sizing: The ancillary register can be sized to produce exact multiplication or adjusted to implement multiplication modulo a power of two.Changing the ancillary-register size and corresponding R_l gates determines the desired modulus.

8 Controlled Weighted Sum

The controlled weighted-sum circuit combines QFT multiplication blocks to accumulate products of superposed inputs and weights, supporting fixed-point precision and inner products.

  • Circuit architecture: A quantum circuit computes weighted sums by combining controlled multiplication blocks for each input weight and value.The architecture is similar to the QFT multiplication circuit and accumulates the contributions in a Fourier-transformed ancillary register.
  • Circuit architecture: Each weight qubit controls whether the corresponding input-value contribution is added, allowing weights and inputs to be superpositions of different values.The construction can therefore represent arbitrary combinations of input weights and numbers.
  • Fixed-point encoding: Fixed-point weights use q qubits and precision 2^-p, covering 0 ≤ a_m ≤ 2^(q−p) − 2^-p.The parameters p and q can be adjusted to select the desired range and precision.
  • Register sizing: For a non-modular weighted sum of N values, the ancillary register uses t = ⌈log2(N2^q2^n)⌉ qubits to preserve precision and prevent overflow.The requirement applies when weights have q bits and inputs have n bits.
  • Applications: The non-modular circuit gives vector dot products, while the modular circuit implements inner products over a finite-field vector space.With one output qubit, the modular result recovers Σ_i a_i · x_i mod 2, and the construction generalizes this to other moduli.

9 Discussion

The paper extends QFT arithmetic with compact adders and multipliers, including weighted-sum circuits for quantum inputs and applications such as inner products and data-processing tasks. It reports gate complexities for these constructions and contrasts their flexibility with classical weighted-sum implementations.

  • QFT adders use O(n^2) gates, while QFT multipliers use O(n^3) gates for n-bit integers.
  • Arithmetic means and weighted averages require the same number of gates as a basic QFT addition.A programmable modular weighted sum can avoid separately computing each weight-value product when elementary gates are classically programmable.
  • For N integers with fixed integer weights, the modular quantum weighted sum has total complexity O(Nn + n^2), versus a classical implementation requiring N multiplications and N sums.Each quantum sum takes O(n) gates, while the direct and inverse QFT contribute the O(n^2) overhead.
  • A weighted-sum circuit for quantum weights and values uses O(Ntqn) gates, becoming O(Nn^3) when n = q = t.For N numbers, the circuit uses as many gates as N multipliers but requires no additions, with an additional O(t^2) QFT overhead for modulo 2^t operations.
  • The controlled weighted adder supports applications including data processing, network planning, machine learning, and inner products.It can work reversibly with superpositions when weights and data are entered as quantum states, and the weighted-sum block can be used inside quantum algorithms requiring inner products.
  • Together, the circuits expand available QFT-based arithmetic operations and demonstrate the potential of phase-encoded computation.
Loading 1411.5949v2…