PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantum Algorithm Implementations for Beginners

Abhijith J., Adetokunbo Adedoyin, John Ambrosiano, Petr Anisimov, William Casper, Gopinath Chennupati, Carleton Coffrin, Hristo Djidjev, David Gunter, Satish Karra, Nathan Lemons, Shizeng Lin, Alexander Malyzhenkov, David Mascarenas, Susan Mniszewski, Balu Nadiga, Daniel O'Malley, Diane Oyen, Scott Pakin, Lakshman Prasad, Randy Roberts, Phillip Romero, Nandakishore Santhi, Nikolai Sinitsyn, Pieter J. Swart, James G. Wendelberger, Boram Yoon, Richard Zamora, Wei Zhu, Stephan Eidenbenz, Andreas Bärtschi, Patrick J. Coles, Marc Vuffray, Andrey Y. Lokhov

arXiv:1804.03719v3cs.ETquant-ph

TL;DR

Quantum programming remains difficult for mainstream computer scientists because its programming model and notation differ fundamentally from classical programming. This review presents 20 algorithms with IBM hardware implementations and finds that real-device results diverge from simulator results because of hardware errors.

  • Problem

    Quantum algorithms and programming remain insufficiently accessible to mainstream computer scientists because their programming model and notation differ fundamentally from traditional programming.

    Source: §1 · p. 4

  • Method

    The review gives self-contained descriptions of 20 quantum algorithms and examines their implementations on IBM quantum hardware alongside simulator experiments.

    Source: §1 · p. 4, §1.1 · p. 4

  • Results

    The implementations reveal differences between simulator and hardware results, including approximately 65% correct answers for one IBM experiment versus perfect simulator accuracy.

    Source: §1 · p. 4, §2.3 · p. 19

  • Takeaways & Limitations

    The review provides an accessible introduction and implementation blueprint for researchers and developers learning quantum algorithms.

    Source: §1 · p. 4

    Hardware noise from gate infidelity and decoherence limits implementation accuracy, with deviations worsening for larger circuits.

    Source: §1.2.1 · p. 13

Abstract

from arXiv · show

As quantum computers become available to the general public, the need has arisen to train a cohort of quantum programmers, many of whom have been developing classical computer programs for most of their careers. While currently available quantum computers have less than 100 qubits, quantum computing hardware is widely expected to grow in terms of qubit count, quality, and connectivity. This review aims to explain the principles of quantum programming, which are quite different from classical programming, with straightforward algebra that makes understanding of the underlying fascinating quantum mechanical principles optional. We give an introduction to quantum computing algorithms and their implementation on real quantum hardware. We survey 20 different quantum algorithms, attempting to describe each in a succinct and self-contained fashion. We show how these algorithms can be implemented on IBM's quantum computer, and in each case, we discuss the results of the implementation with respect to differences between the simulator and the actual hardware runs. This article introduces computer scientists, physicists, and engineers to quantum algorithms and provides a blueprint for their implementations.

1 INTRODUCTION

This introduction frames accessible, implementation-focused quantum programming through concise algebra and quantum-circuit concepts. It also outlines practical IBM hardware and Qiskit execution, organizing selected algorithms by application and paradigm while comparing simulator and hardware behavior.

1 INTRODUCTION

  • The review makes quantum algorithms accessible to mainstream researchers through self-contained explanations and simulator and IBM hardware implementations for small inputs.It focuses solely on IBM’s quantum computing ecosystem and provides accompanying code and implementations.Source: §1 · p. 4

1.1 The quantum computing programming model

  • Quantum computing represents systems as normalized complex vectors, with algorithms expressed as transformations acting on those vectors.The presentation uses higher-level programming abstractions without discussing their quantum-mechanical foundations.Source: §1.1 · p. 4

1.1.1 The qubit.

  • A qubit is a two-dimensional quantum system whose measurement probabilistically yields 0 or 1 according to the squared magnitudes of its amplitudes.Unlike a classical bit, measuring a qubit changes its state.Source: §1.1.1 · p. 4

1.1.2 System of qubits.

  • Systems of n qubits combine through tensor products, producing a state space with dimension 2^n and 2^n computational-basis bit strings.Superposition expresses quantum states as normalized linear combinations of these basis states.Source: §1.1.2 · p. 5, §1.1.3 · p. 5

1.1.3 Superposition and entanglement.

  • Entangled states cannot be decomposed into tensor products of individual-qubit states, and their existence enables quantum computation beyond classical counterparts [128].The section also introduces inner products as overlaps between quantum states.Source: §1.1.3 · pp. 5–6, §1.1.4 · p. 6

1.1.4 Inner and outer products.

  • Inner products yield state overlaps and amplitudes, while outer products produce matrices that represent transformations without explicitly writing exponentially large matrices.Outer-product notation also provides an input-output interpretation for matrices.Source: §1.1.4 · p. 6

1.1.5 Measurements.

  • Measurement converts quantum information into probabilistic classical outcomes, with an n-qubit bit string occurring with probability |⟨x_1...x_n|φ⟩|^2.Partial measurements require renormalizing the resulting state, and noncomputational-basis measurements use a prior transformation.Source: §1.1.5 · p. 7

1.1.6 Unitary transformations and gates

  • Quantum gates are reversible unitary transformations, typically composed from one- and two-qubit operations; {H,T,CNOT} and the Toffoli gate are universal sets [92].The section also defines observables as Hermitian operators whose expectation values represent average measurement outcomes; IBM processors natively measure only the computational basis.Source: §1.1.6 · p. 8, §1.1.7 · p. 10

1.1.7 Observables and expectation values.

  • Measuring complicated observables requires implementing the corresponding basis-changing unitary, whose implementation cost must be included.Not all unitary transformations are easy to implement.Source: §1.1.7 · p. 10

1.1.8 Quantum circuits.

  • Quantum circuits represent qubits as horizontal lines, gates applied from left to right, and measurements with a dedicated meter-symbol gate; a Hadamard followed by CNOT prepares a Bell state.The Bell-state example starts from |00⟩, applies H to the top qubit, then applies CNOT12.Source: §1.1.8 · p. 11

1.1.9 Quantum algorithms.

  • Practical quantum algorithms encode data into input qubits, apply a sequence of quantum gates, and measure qubits to obtain a classically interpretable result.The review describes implementations of these three steps for a variety of quantum algorithms.Source: §1.1.9 · pp. 11–12

1.2.1 The IBM quantum computer.

  • IBM implementations must account for available and physical gate sets, qubit connectivity, and noise from gate infidelity and decoherence.Gate infidelity is typically worse for multi-qubit gates, while decoherence limits circuit depth; the review examines their effects on performance.Source: §1.2.1 · pp. 12–13

1.2.2 Programming the IBM quantum computer: Qiskit library.

  • Qiskit separates circuit design from execution and supports running circuits on the qasm_simulator or IBM quantum processors.It provides a Python-based interface that avoids the graphical interface and supports processors with up to 16 qubits at the time described.Source: §1.2.1 · p. 13, §1.2.2 · p. 14
  • Simulator counts of 507 |00⟩ and 493 |11⟩ matched the Bell-state expectation, whereas hardware produced 0.54 |00⟩, 0.358 |11⟩, and erroneous 01/10 outcomes.The simulator used 1000 runs; the ibmq_16_melbourne processor used 1024 runs, with remaining probability distributed over 01 and 10 because of processor errors.Source: §1.2.2 · p. 15

1.3 Classes of quantum algorithms.

  • Each reviewed algorithm is presented through its problem goal, required gate sequence, and implementation results on IBM’s quantum computer.The review therefore connects algorithmic purpose with circuit construction and hardware execution.Source: §1.3 · p. 16
  • The review classifies selected algorithms by application area and highlights QFT, GO, HHL, VQE, and SIM as central quantum algorithmic paradigms.Because the list is not exhaustive, the algorithms were chosen for relative importance and to provide an overview of the field.Source: §1.3 · pp. 16–17

2 GROVER’S ALGORITHM

Grover’s algorithm searches an unstructured database in O(√N) operations, achieving a quadratic speedup over classical search and being optimal among quantum algorithms [63, 15]. Its oracle-based amplitude amplification was implemented on IBM’s 5-qubit computer, where hardware errors reduced accuracy relative to simulation.

2.1 Problem definition and background

  • Grover’s algorithm finds a marked item with probability > 1/2 using O(√N) operations versus O(N) classically, and is optimal among quantum algorithms [63, 15].The method applies whenever a quantum oracle distinguishes the desired item, although inefficient oracle construction can eliminate practical advantages; specialized factoring algorithms can perform better [113, 114].Source: §2.1 · p. 17

2.3 Algorithm implemented on IBM’s 5-qubit computer

  • The two-bit oracle is implemented with a Toffoli gate, while ibmqx4 requires decomposing that gate into available gates under hardware connectivity constraints.A connectivity-violating implementation produced a deeper Toffoli circuit of depth 23 and the correct answer 48% of the time, compared with depth 13 in the reported circuit.Source: §2.1 · p. 17, §2.3 · p. 19

2.2 Algorithm description

  • Grover’s operator amplifies the marked state by alternating oracle phase reversal with inversion of amplitudes about their mean, requiring about √N iterations.The register is initialized in a uniform superposition, and applying the operator too many times reverses the desired amplification; for two bits, one application finds x∗ with certainty in theory.Source: §2.2 · pp. 18–19

2.3 Algorithm implemented on IBM’s 5-qubit computer

  • The simulator returned x = (1, 1) every time, while ibmqx4 returned it 662/1,024 times, approximately 65%, due to inherent hardware errors.The simulator produced the correct answer every time; the other hardware outcomes occurred 119, 101, and 142 times for (0, 0), (0, 1), and (1, 0), respectively.Source: §2.3 · p. 19

3 BERNSTEIN-VAZIRANI ALGORITHM

The Bernstein–Vazirani algorithm recovers an n-bit hidden string with one oracle query, versus n classical queries, but practical oracle construction can require exponentially many gates. Implementations show exact simulator recovery, while hardware performance is limited by noise, connectivity, and coherence times.

3.1 Problem definition and background

  • The BV algorithm finds the hidden string with one oracle query, compared with n classical queries, yielding an O(n) query-complexity separation.The algorithm assumes an oracle computing the Boolean function, and its final measurement reveals the hidden string with probability 1.Source: §3.1 · p. 20, §3.2 · p. 21
  • The quantum query advantage does not imply faster execution, because implementing an n-bit oracle typically requires O(4^n) simple gates and may have exponentially scaling serial time.Restricted CNOT connectivity requires additional decompositions that can further degrade result quality.Source: §3.1 · p. 20, §3.3 · p. 22

3.2 Algorithm description

  • The algorithm initializes n+1 qubits, applies the oracle U_s and H^⊗n to the first n qubits, then measures the non-ancillary qubits.U_s and H^⊗n are the only operators required, and the initialization matches Grover’s algorithm.Source: §3.2 · p. 21

3.3 Algorithm implemented on IBM’s 5-qubit and 16-qubit computers

  • QNC reduced oracle gate counts by 5×, but 3-bit string “111” still required 428 gates and an estimated 153μs on ibmqx4, exceeding coherence times.For 2-bit strings, QNC produced 41–43 gates on ibmqx4 and 66–67 on ibmqx5, with estimated critical paths of approximately 15μs and 28μs, respectively.Source: §3.3 · p. 22
  • 100% of simulator trials produced the exact hidden string, whereas 2-bit hardware runs were noisy and 3-bit circuits were not run physically because execution exceeded coherence times.The hardware tests used 8192 shots; the worst 2-bit noise occurred for “01” on ibmqx4.Source: Figure 10 · p. 23, §3.3 · p. 23

4 LINEAR SYSTEMS

This section introduces quantum linear-system solving for normalized Hermitian systems, explains HHL and its phase-estimation component, and evaluates a 2 × 2 implementation on IBM’s ibmqx4. The simulator matched theoretical expectation values, whereas the actual quantum-computer run did not produce the expected answer.

4.1 Problem definition and background

  • The linear-system problem seeks x in A x = b for a Hermitian matrix A, with x and b rescaled as unit vectors before representing them as quantum states.Such systems arise in science, engineering, finance, economics, differential equations, partial differential equations, and regression.Source: §4.1 · p. 23

4.2 Algorithm description

  • HHL solves linear systems by estimating eigenvalues, applying controlled rotations encoding their inverses, uncomputing phase estimation, and measuring the resulting state’s Pauli expectations.The algorithm requires superposition access to b, outputs a quantum state that collapses upon measurement, and therefore incurs data-loading and readout overheads.Source: §4.2 · p. 24, §4.3 · p. 27

4.3 Phase estimation

  • Phase estimation estimates eigenphases of a controlled unitary using the inverse Quantum Fourier Transform, and its ancillary-qubit count sets both runtime and eigenvalue precision.HHL applies phase estimation to e^iA, assuming the required quantum simulation is available; amplitude amplification can boost the probabilistic success of obtaining |x⟩.Source: §4.3 · pp. 24–27

4.4 Algorithm implemented on IBM’s 5 qubit computer

  • The simulator expectation values matched theoretical ⟨X⟩, ⟨Y⟩, and ⟨Z⟩ values, but ibmqx4 results did not give the expected answer.Nine simulator cases covered three b inputs and three measurements; Fig. 16 compares 4096-shot Z-measurement results from the simulator and ibmqx4.Source: §4.4 · p. 28, Table 3 · p. 29, Figure 16 · p. 29

5 SHOR’S ALGORITHM FOR INTEGER FACTORIZATION

Shor’s algorithm reduces integer factorization to quantum period finding, achieving polynomial-time complexity in the input bit length. An optimized five-qubit implementation factored 15 on ibmqx4, matching the simulator’s periods despite substantially greater hardware noise.

5.1 Problem definition and background

  • Integer factorization has no known polynomial-time classical algorithm in the bit length, underpins RSA security, and is addressed by Shor’s polynomial-time algorithm [113].Shor’s algorithm runs in O(n^3 log n) time and uses O(n^2 log n log log n) gates; prior experiments factored 15 [127].Source: §5.1 · pp. 29–30

5.2 Algorithm description

  • Shor’s algorithm factors an odd integer by finding the even period of modular exponentiation with the Quantum Fourier Transform, then computing greatest common divisors.The QFT produces measurement outcomes related to multiples of M/r, and classical postprocessing extracts factors from x^(r/2) − 1 and x^(r/2) + 1.Source: §5.2 · pp. 30–31

5.3 Algorithm implemented on IBM’s 5-qubit computer

  • The ibmqx4 implementation found periods 0 and 4, enabling recovery of the factors 3 and 5 of 15, while exhibiting substantially more noise than the simulator.The optimized circuit used 5 qubits and 11 gates because the direct circuit required 12 qubits and 196 gates.Source: §5.3 · p. 32

6 MATRIX ELEMENTS OF GROUP REPRESENTATIONS

The section formulates matrix-element estimation for finite-group representations and develops a Hadamard-test algorithm that uses controlled regular representations. It relates irreducible representations to regular ones through group Fourier transforms and demonstrates implementations on IBM hardware and a simulator.

6.1 Problem definition and background

  • Representation theory maps difficult finite-group operations to matrix operations, with finite-group representations expressible as unitary matrices and regular representations providing a constructive example.The regular representation uses group elements as orthonormal basis states; multiplying by a group element permutes those states, so its matrices are permutation matrices and therefore unitary.Source: §6.1 · pp. 33–34

6.2 Algorithm description

  • The Hadamard test estimates ⟨𝜓|U|𝜓⟩ by measuring an ancilla, reducing matrix-element calculation to controlled-unitary implementation.For the regular representation, the required controlled operation can be constructed from CNOT and Z gates; irreducible-representation elements follow when the group Fourier transform is implementable.Source: §6.2 · pp. 36–37

6.3 Algorithm implemented on IBM’s 5-qubit computer

  • IBM 5-qubit circuits implement the test for S2 and A2 representations using X, Z, CNOT, and Hadamard gates, with expected ground-state probabilities of 0.5, 1, 1, and 0.The ancilla is mapped to q1 because the machine architecture permits control from q1 to q0; controlled-Z is decomposed into two Hadamards and one CNOT.Source: §6.3 · pp. 37–38, Figure 21 · p. 38, Figure 22 · p. 38

7 QUANTUM VERIFICATION OF MATRIX PRODUCTS

Matrix product verification asks whether AB=C, improving on the O(n^2) classical high-probability approach through quantum algorithms based on Grover search and amplitude amplification. The described procedure nests quantum searches but requires too many qubits and excessive circuit depth for successful implementation on IBM machines.

7.1 Problem definition and background

  • Quantum verification checks whether the product of two n×n matrices equals a third, while the best classical algorithm succeeds with high probability in time proportional to n^2.Matrix multiplication itself has naive complexity O(n^3), motivating faster verification procedures.Source: §7.1 · pp. 38–39
  • Ref. achieves matrix verification in O(n^7/4), while Ref. further improves this to worst-case O(n^5/3) and expected O(n^5/3/min(w, √n)^1/3).The Ref. algorithm applies over any integral domain with bounded error, where w is the number of wrong entries.Source: §7.1 · p. 39

7.2 Algorithm description

  • Amplitude amplification boosts success probability with O(1/√p) repetitions, a quadratic improvement over the classical O(1/p) repetition strategy.The method generalizes Grover search by amplifying marked states identified through an oracle.Source: §7.2 · p. 39
  • The verification algorithm partitions B and C into √n submatrices, uses amplitude amplification to search for a failing block, and applies Grover search to detect row disagreements.For each block, it samples a random vector x, computes y=B_i x and z=C_i x, then searches for a row where (Ay−z)_j≠0.Source: §7.2 · p. 40
  • The algorithm cannot be successfully implemented on IBM machines because its required qubit count and circuit depth are too large.Its core Grover search procedure is nevertheless implemented elsewhere in the paper.Source: §7.2 · p. 40

8 GROUP ISOMORPHISM

The section defines the abelian group isomorphism problem and presents a Cheung–Mosca quantum approach based on cyclic decomposition and hidden-subgroup computation. It then illustrates a Qiskit period-finding implementation while noting that hardware noise requires circuit optimization.

8.1 Problem definition and background

  • Abelian group isomorphism asks whether two finitely represented groups are related by a bijection preserving their group operation, assuming element labels and group-product oracles are available.The focus is the abelian case, where the operation is commutative; Cheung and Mosca [28] generalize Shor’s approach by decomposing groups into direct products of cyclic subgroups.Source: §8.1 · pp. 40–41

8.2 Algorithm description

  • The algorithm tests isomorphism by decomposing finite abelian groups into cyclic subgroups of prime-power order, with hidden-subgroup generation as its critical quantum step.The hidden-subgroup procedure uses phase estimation, an oracle transformation, inverse Fourier transformation, phase measurement, and sampling to recover generators; its circuit is shown in Fig. 23.Source: §8.2 · pp. 41–42

8.3 Algorithm implemented using Qiskit

  • The Qiskit example implements a period-finding fragment of the hidden-subgroup circuit, but its long circuit is expected to produce inaccurate IBMX4 or IBMX5 results because decoherence and noise dominate.The oracle is a major practical challenge; the example relies on circuits for controlled a^x mod 15, an inverse quantum Fourier transform, and classical continued fractions, while requiring gate-count optimization for hardware.Source: §8.3 · pp. 42–44

9 QUANTUM RANDOM WALKS · 10 QUANTUM MINIMAL SPANNING TREE

The paper introduces discrete quantum walks and demonstrates their implementation on IBM hardware, then presents a Grover-enhanced Borůvka approach for minimum spanning trees with fewer queries than classical algorithms. Hardware noise limits the walk experiment, while the full spanning-tree algorithm was not implemented because of qubit constraints.

9.1 Problem definition and background

  • Quantum graph-property algorithms commonly construct adjacency-matrix oracles, but their qubit and gate requirements can exceed the capacity of current hardware, motivating a simpler walk demonstration.A maximal-clique oracle is described as requiring n^2 data qubits, n^2 ancilla qubits, 6n^2 Toffoli gates, and 2n CNOT gates.Source: §9.1 · p. 44

9.2 Example of a quantum random walk

  • A discrete quantum walk replaces classical transition probabilities with complex amplitudes controlled by a unitary coin operator, making the walk a quantum generalization of a classical random walk.Coin qubits provide movement-choice degrees of freedom required for unitarity.Source: §9.2 · p. 44
  • The walk on a cycle uses an n-qubit position register and one coin qubit, with basis states |k,q⟩ encoding the node and left-or-right choice.For a cycle with N = 2^n nodes, each node has two neighbors, so the coin space has dimension two.Source: §9.2 · p. 45
  • Each walk step alternates a coin operator, implemented here by a Hadamard gate, with a shift operator that moves the walker and flips the coin state.A p-step walk is represented by (SC)^p.Source: §9.2 · p. 45

9.3 Algorithm implementation using Qiskit on IBM Q

  • The experiment implemented a four-vertex cycle in Qiskit and executed it on both a simulator and IBM’s five-qubit ibmq_vigo processor.The starting vertex was labeled 0, and the walk was tested for multiple steps.Source: §9.3 · p. 45
  • After four steps, the simulator concentrated probability on |100⟩, whereas ibmq_vigo produced |100⟩ with only 21.7% probability; after one step, it produced |111⟩ with 33.5% and |010⟩ with 28.5%.The four-step degradation was attributed to the circuit’s large depth.Source: §9.3 · p. 46

10.2 Algorithm description

  • The quantum minimum-spanning-tree algorithm requires O(√n m) queries, compared with O(m log n) time for classical Borůvka’s algorithm, and combines Borůvka with Grover search.The supplied passage states the quantum query bound as O(√n m).Source: §10.2 · p. 48
  • Borůvka’s method repeatedly finds each tree’s minimum-weight outgoing edge and merges the resulting disjoint trees, with at most log n iterations.The classical implementation performs k searches per iteration and inspects the m edges once in a sweep.Source: §10.2 · p. 49

11 QUANTUM MAXIMUM FLOW ANALYSIS … Heuristics and approximation algorithms.

The paper explains quantum acceleration for maximum flow through Grover-assisted layered-graph construction, then introduces QAOA as a hybrid quantum-classical heuristic for combinatorial optimization and MaxCut. It relates these methods to classical augmenting-path algorithms, approximation guarantees, Hamiltonian formulations, and implementation limitations.

11.1 Problem definition and background

  • Maximum flow is obtained by repeatedly augmenting residual paths and permitting reverse flow, as illustrated by a network whose final flow is 5.The example augments paths [s,v,t], [s,w,t], and [s,v,w,t], with residual capacity determining the final augmentation.Source: §11.1 · pp. 51–52
  • Edmonds–Karp improves maximum-flow convergence by choosing shortest augmenting paths, while the quantum-accelerated version replaces the associated 𝑚2 term with √𝑚.Shortest-path selection uses breadth-first search to build layered residual subgraphs; quantum acceleration targets this step.Source: §11.1 · pp. 51–52

11.2 Algorithm description

  • Ambainis and Spalek’s quantized Edmonds–Karp algorithm uses generalized Grover search to assign vertex layers and construct the layered subgraph needed for shortest augmenting paths.The procedure initializes the source layer, searches for unassigned neighbors, and assigns each discovered vertex the next layer number.Source: §11.2 · p. 52
  • The full quantum layered-graph circuit is impractical on IBM hardware because its required circuit size is too large, although Grover search provides the algorithm’s central implementable component.The oracle marks neighbors whose layer entries remain ∞, without requiring prior knowledge of how many such entries exist.Source: §11.2 · p. 53

12.1 Problem definition and background

  • MaxSat and related combinatorial optimization problems maximize satisfied binary clauses and are computationally challenging, with MaxSat being NP-Hard in general.MaxCut is a concrete case that partitions graph vertices into two sets to maximize crossing edges; the example achieves a cut of size five.Source: §12.1 · p. 53, The Maximum Cut Problem · p. 53

The Maximum Cut Problem.

  • MaxCut can be represented with binary or spin variables, and its objective is equivalent to finding the ground state of an Ising antiferromagnet.The transformation x_i = (z_i + 1)/2 enables replacing spin variables with Pauli Z operators in a quantum Hamiltonian.Source: The Maximum Cut Problem · pp. 53–54

Heuristics and approximation algorithms.

  • Because MaxCut is NP-hard, heuristics lack universal performance guarantees, whereas approximation algorithms provide instance-wide ratios; Goemans–Williamson achieves 0.878.. and a low-degree refinement reaches 0.932...Assuming NP ⊄BQP, QAOA is presented as a quantum heuristic; a proven 0.692.. approximation is known for 3-regular graphs.Source: Heuristics and approximation algorithms · pp. 54–55

12.2 Algorithm description

Parameter finding and relation to the adiabatic theorem. · A closer look at the quantum Hamiltonians.

QAOA parameters can be found through grid or heuristic classical optimization, and increasing rounds connects to an adiabatic discretization whose ideal expectation approaches the optimum. Its Hamiltonian formulation enables commuting clause unitaries, restricted angle domains, and implementations on IBM hardware, where noise can erase multi-round gains.

Parameter finding and relation to the adiabatic theorem.

  • Estimating or sampling QAOA performance requires m log m samples to obtain at least one solution near expectation and m^3 samples for precise expectation estimation, reducible to m^2 in a stated bounded-degree MaxCut regime.The m^2 reduction applies when the objective distribution is concentrated around its expectation for bounded-degree graphs with a small number r of rounds.Source: Parameter finding and relation to the… · p. 56
  • In the ideal noise-free setting, optimal QAOA expectation values are non-decreasing with rounds and converge to the optimum as r→∞, via adiabatic-algorithm discretization.The adiabatic construction uses H(t)=(1−t/T)B+(t/T)C and sufficiently slow evolution under the stated spectral-gap condition; alternating B and C with Σ_k β[k]+γ[k]=T yields Trotterization.Source: Parameter finding and relation to the… · p. 56
  • QAOA can outperform adiabatic algorithms on some problems, but beyond the 1-round 0.692.. MaxCut approximation for 3-regular graphs, QAOA remains heuristic; small-round methods face an ≈0.834 limitation.For larger node degrees and r∈o(log n), the cited limitation applies to sublogarithmic-round QAOA.Source: Parameter finding and relation to the… · p. 57
  • For small constant r, exhaustive grid search is polynomial because the expectation landscape lacks narrow peaks, whereas larger-r optimization is non-convex and uses gradient, control, interpolation, basin-hopping, or variational methods.Basin-hopping alternates local optimization with larger random perturbations to explore new basins, but classical methods generally lack guarantees of reaching optimal parameters.Source: Parameter finding and relation to the… · p. 57

A closer look at the quantum Hamiltonians.

  • Combinatorial objectives become quantum Hamiltonians by converting binary variables to spins and replacing constants with identity operators and spins with Pauli Z_i operators.For MaxCut, each clause involves two variables, and all clauses share one structure, simplifying circuit construction.Source: A closer look at the quantum… · p. 57
  • MaxCut clause Hamiltonians are diagonal and commuting, so e^{-iγ(C12+C23)} factorizes into the product of individual clause unitaries.For the 2-edge path, C=C12+C23 with C12=1/2(Id−Z1Z2) and C23=1/2(Id−Z2Z3).Source: A closer look at the quantum… · pp. 57–58
  • Hamiltonian periodicity restricts angle searches to 0≤γ≤2π and 0≤β≤π, with MaxCut symmetries narrowing the β domain further through global-phase and cut-set equivalences.The β periodicity follows from the mixing Hamiltonian, while the MaxCut-specific transformation swaps all variable values without changing the expectation value.Source: A closer look at the quantum… · p. 58

12.3 QAOA MaxCut on ibmqx2

  • On ibmqx2, a MaxCut edge unitary is implemented with two CNOT gates and one U1(−γ) gate, while the mixing operation uses U3(2β_k,−π/2,π/2) on each qubit.The resulting circuit implements 2-round QAOA for the Triangle plus Edge graph, with edge gates replicated across graph edges and U3 layers implementing e^{-iβB}.Source: §12.3 · p. 59, Figure 37 · p. 60

Towards practical relevance. · 13 QUANTUM PRINCIPAL COMPONENT ANALYSIS

The review highlights unresolved practical limits for QAOA and presents a two-feature quantum PCA implementation constrained by five-qubit hardware. The simulator reproduced the expected PCA result, whereas IBM’s quantum computer produced non-real, incorrect eigenvalues.

Towards practical relevance.

  • QAOA has not achieved quantum advantage because current devices remain too noisy and problem instances too small, leaving speedup and improved approximation ratios unresolved.Noise, hardware connectivity, compilation choices, and limited evaluations can affect sampled-solution quality and attainable performance.Source: Towards practical relevance · p. 62

13.1 Problem definition and background

  • PCA identifies features explaining the largest variance by diagonalizing the covariance matrix and retaining those associated with the n largest eigenvalues.The retained dimensionality n depends on the desired reduction.Source: §13.1 · pp. 62–63
  • The PCA example uses housing features such as bedrooms and square footage, centers and rescales the data, and computes the classical covariance matrix and eigenvalues before quantum processing.The example contains 15 Los Alamos houses, with square footage divided by 1000 and both features mean-centered.Source: §13.1 · pp. 62–63

13.2 Algorithm description

  • The quantum PCA approach encodes the covariance matrix as a density matrix, prepares copies, applies exponential SWAP, and uses phase estimation to determine eigenvalues.For IBM’s five-qubit limit, the implementation instead purified a two-feature state, prepared two copies, measured purity with an ancilla, and recovered the covariance eigenvalues classically.Source: §13.2 · p. 64
  • The two-feature implementation converts raw data into Σ, normalizes it as ρ = Σ/Tr(Σ), prepares purified copies, measures purity with controlled-SWAP, and classically computes eigenvalues.The purity circuit uses a Hadamard-test structure in which the ancilla’s final Z expectation equals P = Tr(ρ^2).Source: §13.2 · pp. 64–65

13.3 Algorithm implemented on IBM’s 5-qubit computer

  • The IBM circuit used 16 CNOT gates, and limited connectivity required reversing CNOT direction and replacing another CNOT with a four-CNOT construction.Connectivity also determined the ancilla and controlled-SWAP target assignments.Source: §13.3 · p. 65, Figure 40 · p. 66
  • IBM’s 5-qubit quantum computer returned e1 = 0.838943 + 0.45396i and e2 = 0.838943 − 0.45396i, violating the real non-negative eigenvalue requirement.By contrast, the simulator essentially gave the correct answer with 40960 trials.Source: §13.3 · p. 66

14 QUANTUM SUPPORT VECTOR MACHINE · 15 QUANTUM SIMULATION OF THE SCHRÖDINGER EQUATION

The paper presents quantum implementations of least-squares SVM and one-dimensional Schrödinger-equation simulation. The SVM offers logarithmic complexity but an unreliable kernel-matrix step on current processors, while the Schrödinger simulation uses Fourier-based phase updates and shows phase-dependent hardware errors.

14 QUANTUM SUPPORT VECTOR MACHINE

  • Quantum SVM computes the linear kernel matrix with a quantum inner-product algorithm, solves the LS-SVM linear system quantumly, and classifies queries using the trained qubits [102].Its overall complexity is O(log N M), compared with O(M^2(M + N)) classically.Source: §14 · p. 66
  • The quantum SVM procedure computes K_ij = x_i·x_j, obtains |b, α⟩ by quantum linear-system solving, and classifies the query against those training results [84], [60], [102].The kernel calculation cannot be performed reliably on currently available quantum processors, although the linear-system-solving component can be quantized.Source: §14 · p. 67

15.1 Problem definition and background

  • Schrödinger evolution is numerically represented on a discrete grid because analytical solutions are available for only a handful of systems, with position and momentum updates linked by Fourier transformation.The Hamiltonian splitting yields two easily performed steps per time step, and |ψ(x,t_f)|^2 gives the probability of finding a particle at position x.Source: §15.1 · p. 67

15.2 Algorithm description

  • The simulation targets one-dimensional quantum systems and requires an initial wavefunction, time-step size, number of steps, computational-basis phase shifts, and potential function V.It outputs the wavefunction at t_f = Tδt after evolution under the Schrödinger equation.Source: §15.2 · p. 68
  • The Schrödinger simulation encodes an N-point wavefunction grid into n = log2(N) qubits, then repeatedly applies QFT, momentum-space and position-space phase shifts, inverse QFT, and measurement.Repeated measurements estimate |ψ(x,t_f)|^2, and arbitrary phase shifts can use controlled Z or CNOT gates.Source: §15.2 · p. 68

15.3 Algorithm implemented on IBM’s 5-qubit computer

  • The IBM chip experiment measured computational-basis probabilities at ϕ = 0, π/2, π, 3π/2, and 2π, expecting evolution from a Π-function to a uniform function, an endpoint-peaked function, and back.The circuit was run on ibmqx4, with a maximum of 210 executions in a single run.Source: §15.3 · p. 70
  • Observed probabilities were {0.173, 0.393, 0.351, 0.084} for ϕ = 0, {0.295, 0.257, 0.232, 0.216} for ϕ = π/2, and {0.479, 0.078, 0.107, 0.335} for ϕ = π.The final two cases produced {0.333, 0.248, 0.220, 0.199} and {0.163, 0.419, 0.350, 0.068}, respectively, while the ideal ϕ = 0 probabilities were {0, 0.5, 0.5, 0}.Source: §15.3 · p. 70

16 GROUND STATE OF THE TRANSVERSE ISING MODEL

The transverse Ising model ground state is computed with a hybrid variational quantum eigenvalue solver and compared with exact results. A product-state ansatz works in the ordered phase but deviates near the quantum phase transition, while an entangled ansatz nearly reproduces the exact results across the magnetic-field range.

16.1 Variational quantum eigenvalue solver

  • VQES avoids the large-depth and coherence-time demands of quantum phase estimation by using local Hamiltonian terms, but its accuracy depends on the trial state and classical–quantum communication can bottleneck performance.For local interactions, expectation calculations for individual terms can be parallelized and do not require long coherence times.Source: §16.1 · pp. 71–72
  • VQES alternates quantum expectation-value calculations with classical parameter optimization until convergence, combining quantum and classical computing.Its variational parameters are prepared in a quantum state, the Hamiltonian expectation value is measured, and a classical relaxation method updates the parameters.Source: §16 · p. 70, §16.1 · p. 71

16.2 Simulation and results

  • The product-state trial wave function works well in the ordered phase but deviates from the exact solution near the quantum phase transition because it neglects quantum entanglement.Communication bottlenecks prevented implementation on ibmqx4, so this comparison used the Qiskit quantum simulator.Source: §16.2 · p. 73
  • The entangled trial function nearly reproduces the exact ground-state results across the magnetic-field region and improves upon the product-state trial function.The comparison includes ground-state energy and average magnetization against exact, simulator, classical, and mean-field results.Source: §16.2 · p. 74, Figure 47 · p. 74

17 QUANTUM PARTITION FUNCTION

The section motivates quantum partition-function algorithms by the intractability of exact summation and presents an ICCC-restricted algorithm, its QFT-based implementation, and hardware results for a small Ising example.

17.1 Background on the partition function

  • The partition function sums over q^n configurations, is #P-hard, and has no known fully polynomial randomized approximation scheme [58].Partition functions support probability calculations in graphical models such as Markov random fields.Source: §17.1 · pp. 74–76

17.2 A simple example

  • A three-vertex, fully connected q=2 Potts-model example enumerates all configurations, evaluates their Hamiltonians, and substitutes them into the partition-function expression.The example sets J_ij=1 for every edge.Source: §17.2 · p. 76, Figure 49 · p. 76

17.3 Calculating the quantum partition function

  • For ICCC-representable Potts-model graphs, the algorithm uses Gaussian elimination, Shor’s algorithm, and the quantum Fourier transform to obtain a weight spectrum for classical calculation of Z [58].If the cyclic code is not irreducible, efficient partition-function calculation is unavailable under this method.Source: §17.3 · p. 77

17.4 Implementation of a quantum algorithm on the IBM Quantum Experience

  • The IBM Quantum Experience implementation executes the 2-qubit QFT as the first algorithmic step, using the example’s irreducible cocyclic code [1, −1].The input qubits are prepared in |+⟩ states, and output bits are read in reverse order; the circuit is shown in Fig. 51.Source: §17.4 · p. 77, Figure 51 · p. 77
  • P(γ=1)=0.47 and P(γ=3)=0.53 in simulation, compared with hardware probabilities P(γ=0)=0.077, P(γ=1)=0.462, P(γ=2)=0.075, and P(γ=3)=0.386.Low-probability gamma values can be thresholded before calculating the weight spectrum and partition function.Source: §17.4 · pp. 77–78

18 QUANTUM STATE PREPARATION

Quantum state preparation reduces to finding a unitary that maps |0...0⟩ to a desired state and decomposing it into hardware-compatible gates. The section develops single- and multi-qubit constructions, including accuracy–gate-count tradeoffs and Schmidt-based circuits.

18.1 Single qubit state preparation

  • With 30 gates, every single-qubit state lies within chordal distance 0.024 of an exactly obtainable state, enabling approximately 2.5% initialization accuracy.The maximum distance decreases exponentially with gate count, and the method preserves 30-gate states before selecting the closest exact state.Source: §18.1 · pp. 78–79, Figure 52 · p. 79

18.2 Schmidt decomposition

  • Schmidt decomposition prepares an arbitrary 2n-qubit state from one n-qubit state, two n-qubit unitaries, and n CNOT gates.The construction follows from decomposing the coefficient matrix by singular values, with the resulting circuit implementing the required Schmidt sum.Source: §18.2 · pp. 79–81

18.3 Two-qubit state preparation

  • An arbitrary two-qubit state can be prepared using three one-qubit gates and exactly one CNOT gate.This is the simplest instance of the Schmidt-decomposition circuit and covers superpositions of the four computational basis states.Source: §18.3 · p. 81

18.4 Two-qubit gate preparation

  • Any two-qubit unitary can be implemented with precisely three CNOT gates and seven one-qubit gates, using a decomposition based on Makhlin invariants.The section provides a recipe for selecting the one-qubit gates so the circuit realizes any element of SU(4).Source: §18.4 · p. 81

18.5 Four qubit state preparation

  • Any four-qubit state can be initialized using nine CNOT gates and 17 one-qubit gates through a four-stage Schmidt-decomposition circuit.The stages initialize a two-qubit Schmidt component, add two linking CNOTs, and apply generic circuits for the associated orthonormal-basis unitaries; processor and simulator results are reported separately.Source: §18.5 · p. 82

19 QUANTUM TOMOGRAPHY

Quantum tomography reconstructs density matrices from repeated measurements and certifies quantum-state and gate performance under noise. The paper surveys reconstruction methods and implements maximum likelihood tomography on IBM QX, revealing substantial decoherence and noise in one- and two-qubit experiments.

19.1 Problem definition and background

  • Quantum tomography reconstructs the density matrix ρ from repeated algorithm runs and informationally complete measurements, because a single copy cannot determine a general quantum state.Noise produces mixtures of states, requiring density-matrix rather than single-state representations.Source: §19.1 · pp. 83–84

19.2 Short survey of existing methods

  • Existing methods trade speed, physical validity, statistical assumptions, and prior selection, with no universally best general method; maximum likelihood remains the most widely discussed.Linear inversion can yield non-positive estimates, linear regression assumes approximately Gaussian residuals, and Bayesian priors are difficult to choose in practice.Source: §19.2 · p. 85

19.3 Implementation of the Maximum Likelihood method on 5-qubit IBM QX

  • The paper implements maximum likelihood tomography with fast gradient descent and optimal 2-norm projection onto the positive-semidefinite matrix space, then applies it to IBM Q.The implementation is designed to enforce physically valid density-matrix estimates efficiently.Source: §19.3 · p. 86

19.3.1 Warm-up: Hadamard gate.

  • In the Hadamard experiment, 96% of observations corresponded to a state near |+⟩_x; decoherence degraded eigenstates and increased occurrences near |−⟩_x.The simulator predicts density-matrix element errors below 10^-3 under ideal noiseless conditions, whereas inserted identity gates expose decoherence.Source: §19.3.1 · pp. 86–87

19.3.2 Maximally entangled state for two qubits.

  • The entangled state occurred with probability 0.87, falling to 0.79 after 18 identity matrices, while the second-most probable eigenstate shifted toward |00⟩, indicating machine bias.These results reveal substantial noise and decoherence in the IBM QX experiments.Source: §19.3.2 · p. 87

20 TESTS OF QUANTUM ERROR CORRECTION IN IBM Q

Experiments on IBM Q found that simple quantum error correction did not improve computation accuracy: added gates and qubits introduced correlated errors that outweighed correction benefits. Although some single-flip errors were corrected, exponential error suppression was not observed.

20 TESTS OF QUANTUM ERROR CORRECTION IN IBM Q

  • The tests indicate that traditional QEC cannot exponentially suppress errors from imperfect gates on the available five-qubit IBM hardware.Encoding one qubit in three may increase the allowed gate count by an order of magnitude at 0.99 fidelity, but the demonstrated correction benefit remained insufficient.Source: §20 · p. 88, §20.1 · p. 89, §20.4 · p. 91

20.1 Problem definition and background

  • The proposed three-qubit encoding protects against isolated bit flips through majority voting, but gate-induced correlated errors can flip multiple encoded qubits together.Independent decoherence motivates exponential suppression assumptions, whereas finite-fidelity gates acting on entangled states generate correlated dynamics that standard correction may not treat.Source: §20.1 · pp. 88–89

20.2 Test 1: errors in single qubit control

  • In the single-qubit-control test, 13 of 1000 runs were wrong, yielding a 1.6% protocol error after 18 gates.This result was consistent with, and slightly better than, the declared 1% single-gate fidelity.Source: §20.2 · p. 90

20.3 Test 2: errors in entangled 3 qubits control

  • In the entangled three-qubit test, measured wrong-event probabilities were P110 = 0.006, P101 = 0.02, P011 = 0.016, and P111 = 0.005.The total probability of any error was 1 − P000 = 0.16, and single-bit-flip outcomes were treated as correctable by majority voting.Source: §20.3 · p. 90

20.4 Discussion

  • QEC increased the wrong-interpretation probability from P1 = 1.3% without QEC to P3 = 4.7% with QEC, despite majority voting.The circuit produced the correct result |000⟩ in 84% of simulations, whereas hardware errors were much larger than expected for uncorrelated flips.Source: §20.4 · pp. 90–91

Related papers

Loading 1804.03719v3…