PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantum Algorithms Revisited

Richard Cleve, Artur Ekert, Chiara Macchiavello, Michele Mosca

arXiv:quant-ph/9708016v1quant-ph

TL;DR

The paper seeks a unifying view of quantum algorithms through multi-particle interference. It reviews and relates algorithms to phase estimation, and presents a universal construction for generating prescribed interference patterns with arbitrary precision.

  • Problem

    The paper considers how viewing quantum computation as multi-particle interference can provide a simple, unifying picture of known quantum algorithms.

    Source: §1 · p. 1

  • Method

    The paper uses multi-particle interference to review quantum algorithms and relates the approach to phase estimation, alongside a universal construction for prescribed interference patterns.

    Source: §1 · p. 1, §8 · p. 16

  • Results

    Classical functions evaluated on quantum superpositions can generate arbitrary interference patterns with prescribed precision, and the paper provides an explicit universal construction.

    Source: §8 · p. 16

  • Takeaways & Limitations

    Viewing quantum computation as multi-particle interferometry gives a simple, unifying picture of known quantum algorithms.

    Source: §1 · p. 1

    The order-finding setup assumes an additionally supplied prepared state of a specified form.

    Source: §6 · p. 12

Abstract

from arXiv · show

Quantum computers use the quantum interference of different computational paths to enhance correct outcomes and suppress erroneous outcomes of computations. A common pattern underpinning quantum algorithms can be identified when quantum computation is viewed as multi-particle interference. We use this approach to review (and improve) some of the existing quantum algorithms and to show how they are related to different instances of quantum phase estimation. We provide an explicit algorithm for generating any prescribed interference pattern with an arbitrary precision.

1. Introduction

The introduction frames quantum computation as multi-particle interference: entanglement prepares nontrivial superpositions, while interference evolves them toward outputs. This viewpoint gives a simple, unifying picture of quantum algorithms, with phase shifts arising from logic-gate operations.

1. Introduction

  • Entanglement encodes data in non-trivial multi-particle superpositions, and interference evolves inputs into outputs by modifying those superpositions.The passage characterizes multi-particle interference as an inherently quantum process with no classical analogue.Source: §1 · p. 1
  • Viewing quantum computation as multi-particle interferometry gives a simple, unifying picture of known quantum algorithms.In this view, phase shifts result from operations of quantum logic gates.Source: §1 · p. 1
  • The paper proceeds from Deutsch’s problem and its generalisations to the quantum Fourier transform, phase estimation, order-finding, and a construction for arbitrary interference patterns.The final construction is described as generating any desired interference pattern with arbitrary accuracy.Source: §1 · p. 3

2. Deutsch’s Problem

Deutsch’s problem asks whether one function evaluation can distinguish constant from balanced Boolean functions. The algorithm uses a quantum network to obtain that global property with certainty from a single evaluation.

2. Deutsch’s Problem

  • The problem asks for the global property of whether f(0) and f(1) are equal, despite allowing only one evaluation of f.Classical intuition requires evaluating both inputs to determine this property.Source: §2 · p. 4
  • A single quantum evaluation of the f-controlled-NOT distinguishes balanced from constant functions, although one classical evaluation cannot.The quantum network applies the f-controlled-NOT to a superposition.Source: §2 · p. 4
  • A measurement of the first qubit distinguishes constant from balanced functions with certainty.The final state is |0⟩ for constant functions and |1⟩ for balanced functions.Source: §2 · p. 5
  • The improved algorithm always returns the correct “balanced” or “constant” answer, unlike Deutsch’s earlier algorithm, which is inconclusive with probability 1/2.The passage also notes that Alain Tapp independently discovered a similar algorithm.Source: §2 · p. 5
  • Deutsch’s result is presented as an instance of a recurring algorithmic sequence: a Fourier transform, an f-controlled operation, and another Fourier transform.The sequence can be a critical component of a larger algorithm, as in Grover’s database search.Source: §2 · p. 6

3. Generalisations of Deutsch’s Problem

The section extends interference-based query algorithms to promised Boolean-function problems, recovering function properties or hidden information with one or a small number of quantum evaluations. It covers Deutsch–Jozsa classification, Bernstein–Vazirani recovery, multi-output parity, and affine functions.

Multi-output parity

  • One quantum evaluation solves the promised constant-or-evenly-balanced output-parity problem, for which a classical algorithm needs 2^(n−1) + 1 evaluations in the worst case.The promise concerns whether the output values have constant parity or are evenly balanced by parity.Source: §3 · pp. 6, 8

Deutsch–Jozsa generalization

  • One f-controlled-NOT evaluation classifies a promised constant-or-balanced Boolean function with certainty, improving on the original two-evaluation algorithm.The measurement distinguishes a zero amplitude for the all-zero control state in the balanced case from its nonzero amplitude in the constant case.Source: §3 · p. 7

Bernstein–Vazirani problem

  • One f-controlled-NOT evaluation determines a in the Bernstein–Vazirani problem, whereas classical determination requires at least n evaluations.The function has the form f(x) = (a · x) ⊕ b; measuring the control register yields a.Source: §3 · p. 7

Multi-output parity

  • For a Boolean function with m output bits, the method tests whether output parity is constant or evenly balanced with certainty in one run.The auxiliary register has m qubits, and the first register’s all-zero measurement identifies the constant-parity case.Source: §3 · p. 8

Affine functions

  • For an affine function f(x) = (A · x) ⊕ b, the section describes determining every entry of A with m evaluations.The network can determine c · A for a chosen binary m-tuple c; running it m times with suitable choices recovers A.Source: §3 · p. 8

4. Another Look at the Quantum Fourier Transform

The section presents the quantum Fourier transform over integers modulo 2^m as a network of Hadamard and controlled phase operations. Its output on a basis state factors into single-qubit states, and the inverse transform recovers that basis state.

Factorization

  • The QFT output state is unentangled and factorizes into single-qubit states whose phases encode successive binary fractions of the input.The displayed factors range from the least-significant input bit to the full binary fraction.Source: §4 · p. 8

Network construction

  • Applying the Hadamard and successive controlled-R operations to |a1a2 ··· am⟩ produces the QFT state, with output qubits reversed in order.The reversal is noted in the network caption.Source: §4 · p. 9, Figure 5 · p. 9

Inverse transform

  • Applying the inverse QFT to a state of the specified QFT-output form yields the original basis state |a1 ··· am⟩.The passage states that this extracts the input bits from that state.Source: §4 · pp. 8–9

5. A Scenario for Estimating Arbitrary Phases

The paper considers estimating the phase of an unknown eigenvalue using controlled powers of a unitary and one preparation of its eigenvector. Applying the inverse QFT gives the best m-bit estimate with probability at least 4/π² for a general phase, and the success probability can be amplified by increasing the register size.

Estimation problem

  • The task is to estimate an m-bit φ from controlled-U, controlled-U^2, controlled-U^4, and higher powers, given one preparation of an eigenvector of U.The eigenvalue is e^(2πiφ), and U, its eigenvector, and the eigenvalue are not explicitly known.Source: §5 · p. 10

Method

  • The estimation network uses controlled powers of U to encode φ in a product state, followed by inverse QFT to obtain an estimate.The Figure 6 network is described as the phase-estimation circuit and as the kernel of the order-finding algorithm.Source: Figure 6 · p. 10, §5 · p. 10

Estimation accuracy

  • 4/π² = 0.405… is the stated lower bound on the probability that inverse QFT yields the best m-bit approximation for a general phase φ.When φ is a fraction of a power of two, the inverse QFT instead produces the corresponding state exactly.Source: §5 · p. 11

Success amplification

  • Increasing the register from m to m′ = m + O(log(1/ε)) bits and rounding to the most significant m bits raises success probability to 1 − ε.The passage identifies this as an amplification of the success probability.Source: §5 · p. 11

6. The Order-Finding Problem

The section applies phase estimation to order-finding, where the goal is to find the least positive r such that a^r mod N = 1. It explains how eigenstate preparation and phase estimation recover r, and relates the resulting network to Shor’s algorithm.

6. The Order-Finding Problem

  • Order-finding asks for the minimum positive r with a^r mod N = 1, for relatively prime positive integers a and N with a < N; the passage reports no known classical polynomial-time procedure.Shor’s algorithm solves the problem in polynomial time and gives a polynomial-time quantum algorithm for factoring via an efficient classical randomized reduction.Source: §6 · p. 12
  • With an eigenstate |ψ₁⟩ of eigenvalue e^(2πi/r), phase estimation yields 1/r to 2n-bit precision, sufficient to extract r.Controlled-U^2^j can be implemented using O(n^2) elementary gates.Source: §6 · p. 12
  • Although |ψ₁⟩ is not straightforward to prepare, the easy state |1⟩ can replace a randomly chosen eigenstate because an imagined eigenbasis measurement commutes with the controlled operations.The imagined measurement at the end does not affect the control-register outcome.Source: §6 · pp. 12–13
  • A uniformly random eigenstate |ψₖ⟩ yields k/r to 2n-bit precision; continued fractions recover r when k and r are coprime, and verification permits retries otherwise.The expected number of random trials is O(log n).Source: §6 · p. 12
  • Shor’s network estimates an eigenvalue of the operation mapping |x⟩ to |ax mod N⟩, and is identical to the network derived through Kitaev’s methodology.The controlled-U^2^j operations correspond to repeated squaring in modular exponentiation.Source: §6 · p. 13

7. Generating Arbitrary Interference Patterns

The section describes a construction for producing prescribed interference patterns: conditional operations on an auxiliary register induce relative phases on control-register states. A shared auxiliary eigenstate provides the phase kick-back needed for this construction.

7. Generating Arbitrary Interference Patterns

  • The construction uses a control register containing states to interfere and an auxiliary register used solely to induce relative phase changes.It aims to generate specific interference patterns with arbitrary precision via function evaluations.Source: §7 · p. 13
  • When conditional operators Uₓ share auxiliary eigenvector |Ψ⟩ with eigenvalue e^(2πiφ(x)), applying them induces phase e^(2πiφ(x)) on each control state |x⟩.The controlled unitary acts on the auxiliary register conditioned on the first register.Source: §7 · p. 13
  • For Deutsch’s conditional Uf, the operators Uf(0) and Uf(1) share eigenstate |0⟩−|1⟩, illustrating the common-eigenstate construction.The operators map |y⟩ to |y ⊕ f(0)⟩ and |y⟩ to |y ⊕ f(1)⟩, respectively.Source: §7 · p. 14
  • Using an eigenstate in the auxiliary register allows the same state to be used for any phase φ; reversible addition of φ(x) can then induce the desired phase on a superposition of control inputs.Which functions φ(x) are useful and how to compute them depend on the problem.Source: §7 · p. 15

8. Conclusions

The conclusion frames several quantum algorithms as multi-particle interference processes, with Fourier transforms and function evaluations producing phase-dependent interference. It also presents eigenvalue estimation as a useful perspective and arbitrary-precision interference-pattern generation as a construction.

8. Conclusions

  • Several algorithms share a sequence of Fourier transform, function evaluation inducing phase shifts, and a second Fourier transform that brings differently phased paths together.The last Fourier transform is essential to guarantee interference among the paths.Source: §8 · pp. 15–16
  • The authors argue that estimating or determining operator eigenvalues on eigenstates may help explain quantum algorithms and may prove useful in constructing new or improving existing algorithms.They identify Simon’s, Shor’s discrete logarithm, Boneh–Lipton, and Kitaev’s Abelian Stabiliser algorithms as examples that can be deconstructed similarly.Source: §8 · p. 16
  • The paper describes an explicit universal construction that uses classical-function evaluations on quantum superpositions to generate prescribed interference patterns with arbitrary precision.The conclusion presents this as a demonstrated capability of the paper.Source: §8 · p. 16

Appendix A. Cracking RSA

The appendix describes a route to decrypting a particular RSA instance by finding the order of its ciphertext, then solving a congruence for the private exponent. This route does not require that factoring be possible from the resulting order.

Appendix A. Cracking RSA

  • The appendix frames RSA root-finding as computing P modulo N from P^e, e, and N, and notes that whether solving this problem necessarily yields a randomized polynomial-time factoring algorithm remains open.It states that factoring does give a polynomial-time algorithm for finding e-th roots for e relatively prime to φ(N).Source: Appendix A · p. 16
  • Given the prime factorization of N, the appendix computes φ(N) and then finds d with ed ≡ 1 mod φ(N), yielding P^ed ≡ P modulo N.The passage distinguishes this factorization-based route from recovering a particular plaintext using its order.Source: Appendix A · p. 16
  • For ciphertext C = P^e, order(P) equals order(P^e) and order(C) when e is relatively prime to φ(N), so Shor’s algorithm can find order(P).The passage then obtains d satisfying de ≡ 1 modulo order(P) and uses it to recover P, regardless of whether this permits factoring N.Source: Appendix A · p. 16

Appendix B. Concatenated Interference

Grover’s search is presented as a concatenated interference network that repeats a generic transform–controlled-operation–transform sequence. For a tagged value k, the quantum algorithm uses fewer oracle evaluations than the stated classical search bound, and the repeated network outputs k with probability greater than 0.5.

Appendix B. Concatenated Interference

  • The generic sequence repeats a Hadamard/Fourier transform, an f-controlled-U operation, and another Hadamard/Fourier transform.The passage introduces this sequence as a pattern underlying quantum algorithms and illustrates it with Grover’s database search.Source: Appendix B · p. 16
  • For 50% success, a classical algorithm needs at least 2n−1 evaluations of fk, while a quantum algorithm needs O(2n/2) evaluations.The task is to find the unique k for which the oracle function fk marks its input.Source: Appendix B · p. 17
  • Repeating Grover’s basic sequence 2n/2 times yields the tagged value k at the output with probability greater than 0.5.The sequence is depicted as a network representation of Grover’s algorithm.Source: Figure 7 · p. 17

Appendix C. Amplifying success probability when estimating phases

The appendix analyzes phase estimation for a real phase φ in [0,1) that is not a fraction of 2m. It gives a lower bound on the probability of obtaining the closest m-bit approximation and states a precision–confidence guarantee for a specified choice of m.

Appendix C. Amplifying success probability when estimating phases

  • The analyzed phase φ lies in [0,1) and is not a fraction of 2m.These conditions define the scope of the result stated in the appendix.Source: Appendix C · p. 17
  • After inverse QFT on (5.1), the closest m-bit approximation |a⟩ is measured with probability at least 4/π2.The passage gives this bound as approximately 0.405.Source: Appendix C · p. 17
  • An estimate within 1/2n+1 of φ is obtained with probability at least 1−ε using the stated choice of m.The passage begins specifying m as n + ⌈log2(1… but the expression is incomplete in the supplied text.Source: Appendix C · p. 18

Related papers

Loading quant-ph/9708016v1…