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 needs accessible explanations and implementations because its programming model differs fundamentally from classical programming. This review presents self-contained descriptions of 20 quantum algorithms, implements them within IBM’s ecosystem, and compares simulator with hardware behavior. The implementations expose hardware noise and limitations, including cases where error correction failed to achieve exponential error suppression.

  • Problem

    Quantum algorithms and their implementations have been of interest mainly to a small dedicated community, while their physics- and algebra-heavy presentation creates entry barriers for broader audiences.

  • Method

    The review gives succinct, self-contained descriptions of quantum computing and 20 algorithms, focusing on implementation and comparing simulator with IBM quantum hardware experiments.

  • Results

    The review provides implementations across algorithm areas, while hardware results can diverge from simulations because of processor errors and imperfect gates.

  • Takeaways & Limitations

    The paper provides computer scientists, physicists, and engineers with an implementation-oriented introduction and blueprint for quantum algorithms.

  • Takeaways & Limitations

    Traditional quantum error correction did not achieve exponential suppression of errors in the reported IBM 5-qubit experiment.

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

The review lowers barriers to quantum programming by presenting its abstractions and algorithms with accessible algebra, implementations, and hardware comparisons. It introduces qubit states, multi-qubit structure, measurement, circuits, and hardware noise as foundations for implementation.

  • Motivation: Quantum programming is fundamentally different from traditional programming and can impose physics- and algebra-related entry barriers.
  • Scope and approach: The review gives a self-contained, succinct account of quantum computing and basic algorithms focused on implementation, including simulator and IBM hardware experiments.The review focuses on IBM’s quantum computing ecosystem and provides accompanying code and implementations.
  • Quantum states: A qubit is a two-dimensional quantum system whose state is represented as a normalized complex-vector combination of |0⟩ and |1⟩.Measurement yields 0 with probability |α|^2 or 1 with probability |β|^2.
  • Quantum states: Multi-qubit states use tensor products, while entangled states cannot be written as tensor products of individual qubit states.An n-qubit system has a 2^n-dimensional state space, and entanglement enables computations in that space using n physical qubits.
  • Quantum circuits: Quantum circuits apply gates in sequence and end with measurements that produce classically interpretable results.The Bell-state example prepares an entangled two-qubit state from |00⟩ before measurement.
  • Implementation and noise: 1000 simulator runs produced {'11': 493, '00': 507}, whereas 1024 hardware runs produced |11⟩ with probability 0.358 and |00⟩ with probability 0.54.Hardware also produced 01 and 10 outcomes, which are not part of the Bell state and are attributed to processor errors.

2 GROVER’S ALGORITHM

Grover’s algorithm searches for a marked item by repeatedly amplifying its amplitude, achieving a quadratic query advantage over classical search. Its IBM implementation illustrates how hardware decomposition, connectivity, and noise affect results.

  • Problem definition and background: Grover’s algorithm finds a marked item with O(√N) operations, compared with O(N) classically.This quadratic speedup is optimal among quantum search algorithms.
  • Algorithm description: The algorithm requires an oracle that recognizes the target and a diffusion operator that reflects amplitudes about their mean.The oracle lowers the target amplitude, while diffusion raises it above the mean and lowers the others.
  • Algorithm description: For a two-bit search, one Grover-operator application is sufficient to find the unique target with certainty in theory.Larger searches require repeated applications, and the oracle must be implemented as a reversible quantum circuit.
  • Algorithm implemented on IBM’s 5-qubit computer: The IBM circuit uses state preparation, a decomposed Toffoli gate, diffusion, and measurement, while respecting constrained CNOT connectivity.The Toffoli occupies 13 time slots and diffusion occupies 7 time slots in the implemented circuit.
  • Algorithm implemented on IBM’s 5-qubit computer: 65% of 1,024 IBM shots returned the correct answer, whereas the simulator returned it every time.The reported deviation is attributed to hardware errors and is expected to worsen for larger circuits.
  • Algorithm implemented on IBM’s 5-qubit computer: 48% correctness resulted when non-connected CNOTs produced a deeper Toffoli implementation of depth 23 instead of 13.The connectivity-violating circuit performed worse than the circuit designed for the processor topology.

3 BERNSTEIN-VAZIRANI ALGORITHM

The Bernstein–Vazirani algorithm recovers an n-bit hidden string with one oracle query, contrasting with the n classical queries required. Its implementation shows both exact simulator behavior and hardware costs from gate decomposition and connectivity.

  • Problem definition and background: The Bernstein–Vazirani algorithm finds the hidden string with a single oracle application, giving quantum query complexity one.The final measurement reveals the hidden string with probability 1 in the ideal algorithm.
  • Problem definition and background: Classically, recovering an arbitrary n-bit hidden string requires n queries because each function call returns only one bit of information.The paper contrasts this with the quantum algorithm’s one-query complexity.
  • Algorithm implementation: Constructing the oracle can require O(4^n) simple gates, so the main speedup concerns query complexity rather than necessarily total execution time.The oracle’s serial execution time can scale exponentially in the worst case.
  • Algorithm description: The algorithm initializes n+1 qubits, applies the hidden-string oracle, applies H⊗n to the first n qubits, and measures them.The oracle performs |x⟩|q⟩→|x⟩|q⊕⟨s,x⟩⟩.
  • Algorithm implementation: For 2-bit hidden strings, QNC circuits used 36–38 gates on an ideal all-to-all topology and 41–43 gates on ibmqx4.The reported critical-path estimate on the ideal topology was approximately 17 μs.
  • Algorithm implemented on IBM’s 5-qubit computer: The local simulator recovered tested hidden strings exactly, while ibmqx4 results showed the worst noise for string “01”.The hardware comparison used all 1-bit and 2-bit strings on ibmqx4 and ibmqx5.

4 LINEAR SYSTEMS

Quantum linear-system solving expresses the solution as a quantum state and uses phase estimation, controlled rotations, and inverse phase estimation. The review implements a 2×2 example and compares simulator expectations with theory.

  • Problem definition and background: The linear-system problem asks for x in A x = b, with A assumed Hermitian and x and b represented as quantum states.The problem arises in applications including differential equations, partial differential equations, and regression.
  • Problem definition and background: HHL targets expectation values involving the solution state rather than directly outputting the full classical vector.This matches the probability-based information typically obtained from quantum measurements.
  • HHL algorithm: Phase estimation estimates eigenvalues, controlled rotation encodes their inverses, and inverse phase estimation leaves the memory register storing the solution state.The resulting state is post-processed to obtain Pauli-X, Pauli-Y, and Pauli-Z expectation values.
  • Quantum Fourier Transform: The QFT is the central transform used by phase estimation to estimate eigenphases, and the circuit applies its inverse.The review introduces QFT through its relationship to the discrete Fourier transform.
  • Phase estimation: The number of phase-estimation ancillas sets both runtime and eigenvalue bit precision.The estimated eigenvalue is stored in the ancilla register with precision determined by its size.
  • Implementation: The 2×2 HHL implementation uses four qubits: one ancilla, two register qubits, and one memory qubit.The implementation uses controlled rotations with θ=π for λ1 and θ=π/3 for λ2.

5 SHOR’S ALGORITHM FOR INTEGER FACTORIZATION

Shor’s algorithm reduces integer factorization to finding the period of modular exponentiation, using the QFT to extract that period. The review demonstrates factoring 15 on simulation and ibmqx4, with substantial hardware noise.

  • Problem definition and background: Factoring is difficult for large integers, and this difficulty underlies the security of RSA cryptography.No algorithm polynomial in the bit length of the input is known classically.
  • Period finding: Shor’s algorithm factors integers by reducing factorization to period finding for modular exponentiation.An even period enables factor recovery through greatest-common-divisor computations.
  • Period finding: The QFT computes the period of a periodic input in polynomial time, providing the quantum step that makes period finding efficient.Classically, finding the period may require checking as many as N values before a repetition appears.
  • Period-finding circuit: The period-finding circuit applies QFT, modular exponentiation, measurement of the second register, and a second QFT to reveal multiples related to the period.The measured first-register values are multiples of M/r under the simplifying assumption that r divides M.
  • Implementation: The full circuit for factoring 15 required 12 qubits and 196 gates, so the experiment used an optimized 5-qubit, 11-gate version on ibmqx4.The optimized circuit is the one reported for the hardware implementation.
  • Results: The simulator found periods 0 and 4 and thereby recovered factors 5 and 3 of 15; ibmqx4 found the same dominant periods with much more noise.The trivial period 0 was ignored, while period 4 yielded the gcd calculations for the factors.

6 MATRIX ELEMENTS OF GROUP REPRESENTATIONS

This section introduces group representations and shows how the Hadamard test computes their matrix elements as expectation values of unitary operators.

  • Representations: Group representations map group elements to another structure while preserving the group operation.Matrix representations use matrix multiplication, and finite-group representations can be expressed with unitary matrices.
  • Regular representation: The regular representation maps a group of N elements to N×N permutation matrices that are therefore unitary.Group elements are associated with orthonormal basis states, and multiplying by a fixed group element permutes them.
  • Matrix elements: Matrix elements of group representations can be formulated as expectation values ⟨ψ|A|ψ⟩.This reformulation enables quantum computation of the relevant quantities using unitary operators.
  • Limitations: The section contrasts convenient regular representations with their limitation that large groups require multiplication of large matrices.The regular representation is straightforward to construct and retains all group information, but its size can become impractical.
  • Hadamard test: The Hadamard test calculates matrix elements ⟨ψ|U1|ψ⟩ when controlled regular representations can be applied to a quantum register.The review illustrates the algorithm schematically and implements it on IBM hardware.

7 QUANTUM VERIFICATION OF MATRIX PRODUCTS

This section presents quantum verification of matrix products, using nested Grover searches and amplitude amplification to reduce the verification cost relative to classical methods.

  • Problem definition: Matrix product verification asks whether the product of two n×n matrices equals a third matrix.The naive multiplication cost is O(n^3), while the best classical verification algorithm uses time proportional to n^2 with high probability.
  • Quantum approaches: O(n^7/4) is achieved by a Grover-based quantum algorithm for verifying whether two n×n matrices equal a third.A later algorithm gives O(n^5/3) worst-case time and an expected-time bound depending on the number of wrong entries.
  • Amplitude amplification: Amplitude amplification boosts success probability to a constant with O(1/√p) repetitions, compared with O(1/p) classical repetitions.This provides a quadratic speedup over the classical success-probability amplification strategy.
  • Algorithm: The procedure partitions the verification task into smaller subproblems and uses amplitude amplification to search for a failing subproblem.Each smaller verification uses Grover search to find a row where (Ay−z)_j≠0.
  • Implementation boundary: The complete matrix verification algorithm is too large in qubit count and circuit depth for successful implementation on the IBM machines.Its central Grover search procedure is implemented separately in the review.

8 GROUP ISOMORPHISM

This section connects group isomorphism and hidden subgroup problems to quantum period and phase estimation, then demonstrates a period-finding circuit in Qiskit while noting hardware-noise limits.

  • Problem: The group isomorphism problem asks whether two finite groups are equivalent through an isomorphism.The section focuses on the abelian case, where the group operation is commutative.
  • Algorithmic approach: The abelian-group algorithm decomposes each group into cyclic subgroups and compares the resulting structure.The procedure assumes the fundamental theorem of finite abelian groups and uses a group oracle for element products.
  • Hidden subgroup problem: The hidden subgroup problem seeks generators for a subgroup K from a function that is constant and distinct on its cosets.The algorithm prepares superpositions, applies the function unitary, performs an inverse Fourier transform, and measures the first register.
  • Phase estimation: Order-finding, period-finding, and discrete logarithm are presented as extensions of quantum phase estimation.The HSP circuit includes state preparation, function evaluation, inverse Fourier transformation, and phase measurement.
  • Implementation: The review implements a specific period-finding instance in Qiskit, but long circuits on IBM hardware are expected to be dominated by decoherence and noise.Further gate-count optimization is required before the circuit can produce accurate hardware results.

9 QUANTUM RANDOM WALKS

This section explains discrete-time quantum walks and implements one on a four-vertex cycle, showing that deeper circuits produce substantial deviations between simulation and IBM hardware.

  • Applications: The review also describes graph-property applications and a minimum-spanning-tree algorithm requiring O(√nm) queries.The quantum minimum-spanning-tree algorithm combines Borůvka’s algorithm with Grover search.
  • Quantum-walk model: Quantum walks generalize classical random walks by replacing the random process with a unitary coin operation.Discrete-time walks require coin qubits to represent movement choices and preserve unitarity.
  • Algorithm: The walk uses a position register for graph vertices and a coin register for movement choices, with initial state preparation followed by repeated coin and shift operations.For a cycle with N=2^n nodes, n position qubits and one coin qubit are sufficient.
  • Quantum-walk model: A discrete quantum walk alternates a coin operator C with a shift operator S, yielding the p-step operator (SC)^p.The shift moves the walker according to the coin state and flips that state; the review uses a Hadamard coin.
  • Implementation results: 21.7% was the probability of |100⟩ after four steps on ibm_vigo, although |100⟩ remained the most probable state.The simulator concentrated all probability in |100⟩, while the hardware distributed the remainder across other basis states because of the circuit’s large depth.
  • Implementation results: 33.5% and 28.5% were the ibm_vigo probabilities for |111⟩ and |010⟩ after one step, respectively.These are the two states predicted by the simulator for the one-step walk from |000⟩.

11 QUANTUM MAXIMUM FLOW ANALYSIS

Quantum maximum-flow analysis accelerates the shortest-augmenting-path step of Edmonds–Karp by using generalized Grover search to construct layered graph partitions. The review also frames related combinatorial optimization problems, including MaxCut, through binary objectives and quantum Hamiltonians.

  • Classical maximum flow: Edmonds–Karp improves Ford–Fulkerson by repeatedly choosing the shortest augmenting path in the residual network.This choice makes the method practical for integer flows by avoiding slow or nonconvergent behavior associated with arbitrary path choices.
  • Quantum acceleration: √m replaces m^2 in the complexity term when the breadth-first-search step is accelerated in the quantized algorithm.The accelerated step constructs layered subgraphs for finding shortest augmenting paths.
  • Quantum acceleration: The Ambainis–Spalek algorithm uses generalized Grover search to assign vertex layers and build the layered subgraph data structure.Grover search finds all currently unassigned neighbors during the layer-assignment process.
  • Layer construction: The layered-partition procedure initializes the source at layer 0, then iteratively assigns each newly discovered vertex one layer beyond its predecessor.The output is an array L whose entries contain vertex layer numbers.
  • Related optimization formulation: MaxCut maximizes crossing edges by assigning binary variables to graph nodes, with each edge contributing one when its endpoints differ.The binary formulation can be transformed into spin variables and then into a quantum Hamiltonian.

Parameter finding and relation to the adiabatic theorem.

QAOA tunes alternating problem and mixing Hamiltonian angles through a classical optimizer, with increasing rounds improving ideal expectation values but practical hardware gains limited by noise. The MaxCut implementation decomposes clause operations into IBM-compatible gates and shows simulation and hardware outperforming random baselines.

  • Adiabatic relation: In the ideal noise-free setting, the optimal QAOA expectation value is non-decreasing as the number of rounds increases.An r-round circuit can reproduce an (r−1)-round circuit by setting its final angles to zero.
  • Adiabatic relation: For MaxCut on 3-regular graphs, 1-round QAOA achieves a 0.692..-approximation, while no approximation ratios are established for more than one round.Beyond the one-round guarantee, the cited regime is described as purely heuristic.
  • Hamiltonian implementation: MaxCut clause Hamiltonians commute, allowing e^(-iγ(C12+C23)) to factor into separate clause evolutions.This uniform two-variable clause structure simplifies circuit construction.
  • Hardware implementation: The IBM implementation realizes a MaxCut edge gate with two CNOT gates and one U1(−γ) gate, while the mixing operation uses U3(2β_k, −π/2, π/2).The CNOTs compute and uncompute the parity whose phase is shifted.
  • Experimental results: Simulation and Hardware outperform Random for both 1-round and 2-round QAOA, but hardware gains from the second round almost vanish.The longer circuit is more susceptible to gate errors, environmental noise, and qubit decoherence.

Towards practical relevance.

The review’s practical examples show that current quantum hardware remains constrained by qubit counts, connectivity, and noise. A four-qubit PCA implementation fits a five-qubit device but produces nonphysical eigenvalues, while broader QAOA advantage remains unresolved.

  • Hardware constraints: Actual graph instances may not fit planar hardware connectivity, requiring SWAP-based heuristic compilation for sparse graphs and additional challenges for dense graphs or hypergraphs.The review explicitly identifies connectivity as a practical boundary for the studied graphs.
  • Practical relevance: Current devices are too noisy and available problem instances are too small for demonstrated QAOA quantum advantage.Whether QAOA provides significant speedups or better provable approximation ratios remains open.
  • Quantum PCA: A five-qubit IBM device cannot prepare many copies of the density matrix, so the PCA implementation uses two purified copies plus one ancilla.This simplified algorithm targets the special case of two features, where the density matrix is 2 × 2.
  • Quantum PCA: The quantum PCA workflow converts raw data into a normalized covariance-derived density matrix, purifies it, prepares the state, measures purity, and classically post-processes the result.The stated four stages are classical preprocessing, state preparation, purity quantification, and classical post-processing.
  • Quantum PCA results: e1 = 0.838943 + 0.45396i and e2 = 0.838943 − 0.45396i were obtained on IBM’s 5-qubit computer.Because covariance-matrix eigenvalues must be non-negative real numbers, the result is reported as incorrect.

14 QUANTUM SUPPORT VECTOR MACHINE

The review presents quantum support-vector-machine and Schrödinger-equation simulation workflows, while emphasizing that current hardware limits reliable data loading and measurement. The Schrödinger simulation alternates Fourier transforms and phase shifts, but the reported hardware probabilities deviate substantially from ideal results.

  • Quantum support vector machine: Quantum SVM computes a kernel matrix, solves the resulting linear system, and classifies query data using trained quantum states.Its stated overall complexity is O(log N M), while the classical LS-SVM complexity is O(M^2(M + N)).
  • Quantum support vector machine: The quantum SVM’s kernel-matrix inner-product calculation cannot be performed reliably on currently available quantum processors.The linear-system-solving component is identified as quantizable, but kernel evaluation remains the practical obstacle.
  • Quantum simulation: Schrödinger-equation simulation encodes a discretized wave function in n = log2(N) qubits, alternates momentum- and position-space phase shifts, and measures the final state.The evolution uses QFT, an inverse QFT, kinetic phase shifts, and potential phase shifts.
  • Quantum simulation: The simulation pipeline begins with classical wave-function preprocessing, prepares the initial state, iteratively updates it over time steps, and estimates probabilities through repeated measurements.The final probabilities estimate |ψ(x,t_f)|^2.
  • Hardware results: For the φ = 0 case, ideal probabilities {0, 0.5, 0.5, 0} became observed probabilities {0.173, 0.393, 0.351, 0.084}.Other phase settings also showed varying deviations from their expected distributions.

16 GROUND STATE OF THE TRANSVERSE ISING MODEL

The review applies a hybrid variational quantum eigenvalue solver to estimate the transverse Ising model’s ground state energy, comparing trial-state simulations with exact results. Including entanglement substantially improves agreement across the magnetic-field region, while classical–quantum communication and trial-state choice remain limitations.

  • 16 GROUND STATE OF THE TRANSVERSE ISING MODEL: VQES alternates quantum expectation-value calculations with classical parameter optimization until convergence.The procedure prepares a parameterized state, evaluates E = ⟨𝜓|H|𝜓⟩/⟨𝜓|𝜓⟩, updates parameters, and repeats.
  • 16 GROUND STATE OF THE TRANSVERSE ISING MODEL: VQES can exploit local Hamiltonian terms through parallelizable expectation calculations that do not require long coherence times.Its performance can nevertheless be limited by repeated classical–quantum communication, and results depend on the chosen trial wave function.
  • 16 GROUND STATE OF THE TRANSVERSE ISING MODEL: The transverse Ising model transitions from an ordered phase with ⟨𝜎𝑧⟩ ≠ 0 to a disordered phase with ⟨𝜎𝑧⟩ = 0 as the field increases.The transition restores the rotational symmetry associated with R_x.
  • 16 GROUND STATE OF THE TRANSVERSE ISING MODEL: A product-state trial wave function works well in the ordered phase but deviates from the exact solution near the quantum phase transition.The simulation used Qiskit’s quantum simulator because communication bottlenecks prevented implementation on ibmqx4; the discrepancy is attributed to neglected entanglement.
  • 16 GROUND STATE OF THE TRANSVERSE ISING MODEL: An entangled trial wave function nearly reproduces the exact ground-state energy throughout the magnetic-field region and improves on the product-state ansatz.For four spins, the entangled state is prepared with the circuit containing single-qubit operations and CNOT gates.

17 QUANTUM PARTITION FUNCTION

The quantum partition-function algorithm targets the intractable counting problem arising in Potts-model graphical inference. For ICCC-representable graphs, it uses a quantum Fourier transform to obtain data from which the partition function is classically computed, with hardware results differing from simulation.

  • 17 QUANTUM PARTITION FUNCTION: The Potts-model partition function sums over q^n configurations and is generally intractable to calculate or approximate.The passage identifies partition-function calculation as #P-hard and notes that no fully polynomial randomized approximation scheme is known.
  • 17 QUANTUM PARTITION FUNCTION: The algorithm applies to Potts-model graphs representable by an irreducible cyclic cocycle code.The graph’s cyclic code is calculated using Gaussian elimination on its incidence matrix, and the ICCC requirement itself can be checked quantumly.
  • 17 QUANTUM PARTITION FUNCTION: The quantum Fourier transform computes Gauss-sum phases and weight-spectrum information, after which classical computation evaluates the partition function.The QFT supplies the values needed to derive the weight spectrum of the code representing the graph.
  • 17 QUANTUM PARTITION FUNCTION: The implementation demonstrates the first 2-qubit QFT step for a fully connected 3-vertex Ising model satisfying the ICCC requirement.The input code is [1, −1], with n = 3 vertices and k = 2 edges minus connected components.
  • 17 QUANTUM PARTITION FUNCTION: Simulation produced P(𝛾 = 1) = 0.47 and P(𝛾 = 3) = 0.53, whereas hardware produced probabilities 0.077, 0.462, 0.075, and 0.386 for 𝛾 = 0, 1, 2, and 3.Low-probability gamma values can be thresholded before calculating the weight spectrum and partition function.

18 QUANTUM STATE PREPARATION

The review presents practical constructions for preparing arbitrary quantum states, from single-qubit rotations to multiqubit circuits based on Schmidt decomposition. It emphasizes hardware-scale approximation and explicit gate decompositions for two- and four-qubit states.

  • 18 QUANTUM STATE PREPARATION: Preparing an n-qubit state requires finding a unitary mapping the computational basis vector to the target amplitudes and decomposing it into gates.The state space has dimension N = 2^n.
  • 18 QUANTUM STATE PREPARATION: Single-qubit states are represented on the Bloch sphere and prepared using unitary rotations parameterized by angles 𝜃 and 𝜙.Up to a global phase, |𝜓⟩ = cos𝜃|0⟩ + e^i𝜙sin𝜃|1⟩.
  • 18.1 Single qubit state preparation: With 30 gates, every point on the Bloch sphere lies within distance 0.024 of an exactly obtainable state.The construction therefore represents any base state to approximately 2.5% accuracy using about 30 states.
  • 18 QUANTUM STATE PREPARATION: Schmidt decomposition prepares a 2n-qubit state from one n-qubit state, two n-qubit gates, and n CNOT gates.The associated circuit combines U, V, and B with CNOT operations to realize the decomposition.
  • 18 QUANTUM STATE PREPARATION: An arbitrary two-qubit state requires three single-qubit gates and one CNOT, while an arbitrary U(4) gate uses three CNOT gates and seven single-qubit gates.The latter decomposition provides the gate structure needed for four-qubit state initialization.

19 QUANTUM TOMOGRAPHY

Quantum tomography reconstructs a quantum state from repeated preparations and measurements, using informationally complete data and estimation methods. Applied to IBM QX, it reveals noise and decoherence that distort reconstructed states.

  • Tomography goal: Quantum tomography reconstructs ρ from many repeated runs of a quantum algorithm using measurements on the resulting state.A single copy cannot determine a general quantum state; multiple copies are required for characterization.
  • Measurement framework: Informationally complete measurements allow the relations p_i = Tr(ρP_i) to be inverted to reconstruct ρ unambiguously.With finite data, empirical frequencies ω_i = m_i/m are matched to the predicted measurement probabilities.
  • Estimation methods: Linear inversion is fast but can produce estimates with negative eigenvalues because finite-sample inaccuracies make empirical frequencies differ from calculated probabilities.Constrained approaches instead enforce positive semidefiniteness; maximum likelihood does so through a convex optimization problem.
  • Implementation: The review presents an efficient maximum-likelihood implementation using fast gradient descent with optimal 2-norm projection onto the positive semidefinite matrices.The method is then applied to quantum tomography experiments on IBM QX.
  • Experimental results: 96% of measurements observed a state close to |+⟩_x, with the remainder close to |−⟩_x, while added waiting exposed stronger decoherence effects.The leading eigenstate occurred with probability 0.87 after applying 18 identity matrices, rather than the ideal probability 1.
  • Experimental results: IBM QX tomography revealed substantial machine noise and decoherence, including degraded eigenstates and more frequent occurrence of a state near |−⟩_x.The four-qubit state-preparation verification also showed nonzero overlaps with basis states orthogonal to the target.

20 TESTS OF QUANTUM ERROR CORRECTION IN IBM Q

The review tests whether simple quantum error correction can suppress errors on IBM hardware, finding that gate-induced correlated errors limit the benefit of majority-vote encoding.

  • 20.1 Problem definition and background: Quantum error correction encodes a single qubit across three entangled qubits to correct isolated bit-flip errors with majority voting.The scheme assumes errors usually flip only one qubit and uses measurements to correct that error.
  • 20.1 Problem definition and background: Finite gate fidelity, rather than only spontaneous decoherence, produces correlated errors when gates act on strongly entangled states.These errors differ from random, uncorrelated bit flips and can affect multiple encoded qubits together.
  • 20.1 Problem definition and background: The three-qubit encoding cannot correct a rotation-angle error that flips all three qubits, while a nine-qubit encoding was beyond the available hardware.Basic gate errors remain rotation mismatches regardless of how qubits are encoded.
  • 20.2 Test 1: errors in single qubit control: 1.6% error was observed after 18 gates in the single-qubit control test, consistent with or better than the declared 1% single-gate error.The circuit inserted 16 identity-equivalent T-gates while the state was in a superposition before returning it to the measurement basis.
  • 20.4 Discussion: 4.7% error with QEC exceeded the 1.3% error without QEC, despite majority voting intended to suppress errors by about an order of magnitude.Multiple-bit-flip events were much more frequent than expected under uncorrelated bit-flip errors, indicating correlated gate-induced errors.
  • 20.4 Discussion: The brief test found no improvement required for efficient QEC, because the extra gates and qubits increased the probability of wrongly interpreting the final state.Some single-bit errors were corrected, but exponential suppression of errors was not observed.
Loading 1804.03719v3…