Implementation, Verification and Resource Estimation

Introduction

Quantum algorithms become useful only when they can be represented as executable circuits, tested under controlled conditions, and evaluated against realistic hardware constraints. A circuit that is mathematically correct may still be impractical because it has excessive depth, requires unavailable interactions, or produces unreliable results in the presence of noise. Implementation therefore connects algorithmic theory with software development, experimental science and engineering design.

This chapter considers the practical lifecycle of a quantum program: specifying an algorithm, implementing it with a quantum software development kit (SDK), testing it on a simulator, compiling it for a target processor, estimating resources, and validating its output. The discussion applies to common SDK workflows such as Qiskit, Cirq, PennyLane and equivalent platforms. Specific function names vary between SDKs, but the underlying principles are broadly shared.

Learning objectives

By the end of this chapter, a learner should be able to:

1. Construct and execute a small quantum circuit using an SDK and simulator.
2. Distinguish state-vector, shot-based and noisy simulation.
3. Measure circuit width, depth, gate count, qubit count and shot cost.
4. Explain the difference between logical and physical resources.
5. Describe compilation, gate decomposition and connectivity mapping.
6. Estimate sampling uncertainty and interpret fidelity-related measures.
7. Explain the effects of noise, error mitigation and fault tolerance.
8. Design a reproducible verification and benchmarking workflow.

1. From algorithm to executable experiment

A quantum algorithm is normally specified at a logical level. It describes abstract qubits, gates and measurements without assuming a particular processor. An implementation must translate this description into an executable experiment with the following elements:

• a quantum circuit;
• classical input parameters;
• an initial state;
• a measurement basis and observable;
• a simulator or hardware backend;
• a number of repetitions, called shots; and
• procedures for analysing and validating results.

A useful implementation separates three layers:

For example, a Bell-state circuit contains a Hadamard gate followed by a controlled-NOT gate. Its ideal logical state is

If measured in the computational basis, the ideal probabilities are P(00) = 1/2 and P(11) = 1/2, while P(01) = P(10) = 0. An implementation must determine whether the observed results agree with this prediction.

SDK workflow

Although interfaces differ, a typical workflow is:

1. import the SDK and select a backend;
2. allocate qubits and classical bits;
3. apply gates;
4. add measurements or request a statevector;
5. transpile or compile for the backend;
6. execute with a specified number of shots;
7. collect counts or expectation values; and
8. compare results with an analytical reference.

A minimal pseudocode pattern is:

circuit = QuantumCircuit(2, 2)
circuit.h(0)
circuit.cx(0, 1)
circuit.measure_all()
compiled = compile(circuit, backend)
result = run(compiled, shots=1000)
counts = result.counts()

The pseudocode is intentionally SDK-neutral. In real work, the exact measurement syntax, backend selection and result format must be checked against the installed SDK version.

2. Simulation models

State-vector simulation

A state-vector simulator stores the complex amplitudes of a pure n-qubit state. The state has 2ⁿ amplitudes, so memory grows exponentially with n. If each complex amplitude uses 16 bytes, the approximate memory requirement is

This estimate assumes double-precision complex numbers and excludes overhead. For n = 30, the amplitudes alone require approximately 16 × 1,073,741,824 bytes, or 16 GiB. State-vector simulation is valuable for exact or near-exact debugging, but its exponential memory requirement limits the number of qubits.

Shot-based simulation

A shot-based simulator samples measurement outcomes from the state distribution. If an ideal probability for an outcome is p, the observed frequency varies from run to run. For N independent shots, the standard deviation of the estimated frequency p̂ is

This is the binomial standard deviation and assumes independent, identically distributed shots. Since p is usually unknown, p̂ may be substituted for planning purposes. Increasing shots reduces statistical error approximately as 1/√N; it does not remove systematic hardware errors.

Noisy simulation

A noisy simulator adds models of gate errors, readout errors, decoherence and thermal relaxation. Such a model is not automatically a faithful representation of a particular device. Its value depends on calibration data and assumptions. Noisy simulation is useful for testing robustness, comparing mitigation methods and identifying error-sensitive circuit regions.

Tensor-network and stabilizer simulation

Some circuits can be simulated more efficiently than arbitrary state vectors. Stabilizer simulators efficiently represent circuits composed largely of Clifford gates, while tensor-network methods may perform well when entanglement or circuit geometry is limited. Simulation results must therefore be interpreted in relation to the simulator’s mathematical model and supported gate set.

3. Verification of quantum programs

Verification asks whether an implementation performs the intended computation. It is broader than checking whether code runs without an error message.

Analytical and structural verification

For small circuits, calculate the expected state or measurement distribution by hand or with an independent method. Structural checks should confirm:

• the number of qubits and classical registers;
• gate order and control-target direction;
• parameter values and units, especially radians for most SDKs;
• measurement basis;
• initialization assumptions; and
• whether barriers, resets or mid-circuit measurements change the computation.

A useful practice is to test known circuits: preparation of |0⟩ and |1⟩, a single-qubit superposition, Bell states, and inverse-circuit tests. If U is an implemented unitary, applying U followed by U† should return the input state, subject to numerical precision and noise.

Property-based and metamorphic testing

Quantum outputs are probabilistic, so exact string comparison is often inappropriate. Instead, test properties. Examples include:

• probabilities sum to one;
• a circuit and its inverse return the initial state;
• relabelling qubits changes labels consistently but not physical predictions;
• an expected symmetry is preserved; and
• increasing shots reduces random variation without changing the expectation.

These tests are particularly useful when circuits are generated automatically or contain variable parameters.

Statistical comparison

Suppose an ideal distribution is q(x) and an experimental distribution is p(x). A simple total variation distance is

It lies between 0 and 1 for discrete probability distributions. Zero means identical distributions. The measure is useful for distributional comparison, but it does not identify the source of disagreement. For low-probability outcomes, other metrics such as cross-entropy or likelihood-based scores may be more informative.

State fidelity

For pure states |ψ⟩ and |φ⟩, the fidelity is

Here 0 ≤ F ≤ 1, and F = 1 indicates identical physical states up to global phase. This formula applies directly when both states are pure and known. For mixed density matrices, fidelity requires a density-operator definition and cannot be inferred merely from a few measurement counts. In hardware experiments, state fidelity is often estimated through tomography, randomized measurements or application-specific tests, each with sampling and modelling limitations.

4. Resource metrics

Resource estimation should report more than the number of qubits. Important metrics include:

Depth depends on the scheduling convention. Gates acting on different qubits may be placed in the same layer, whereas gates sharing a qubit generally cannot. Thus depth is not necessarily equal to gate count.

A circuit with depth d and gate durations τᵢ has an approximate execution duration

where τℓ is the duration of layer ℓ. This expression assumes layers are sequential and ignores queueing, readout and classical-processing overhead. If all layers have equal duration τ, then T ≈ dτ.

Shot cost and uncertainty

For an observable O with outcomes bounded between −1 and 1, a common estimator is the sample mean

where oᵢ is the outcome of shot i. Its standard error is s/√N, where s is the sample standard deviation. To estimate an expectation value to additive precision ε with confidence level determined by a chosen statistical method, N generally scales as O(1/ε²). The constant depends on the observable, confidence requirement and estimator.

If an expectation value is a weighted sum, E = ∑ⱼ wⱼ Eⱼ, independently estimating each term can make shot allocation important. Terms with larger variance or larger contribution to the final uncertainty may require more shots. A reported answer should state the shot count, confidence method and whether repetitions were independent.

5. Logical and physical resources

Logical resources describe an ideal algorithm. A logical qubit is an abstract information carrier, and a logical gate is an ideal operation in the algorithm’s gate model. Physical resources describe what a processor or fault-tolerant architecture must actually provide.

The distinction matters because one logical qubit may require many physical qubits when encoded for error correction. Likewise, one logical gate may require a sequence of physical gates, syndrome measurements and classical decoding. A resource report should therefore state its level explicitly, for example:

• logical qubits: 8;
• logical two-qubit gates: 120;
• mapped physical qubits: 12;
• compiled physical two-qubit gates: 260; and
• estimated physical circuit depth: 900 layers.

These are different quantities, not contradictory answers.

Ancillas, calibration circuits, readout repetitions, qubit-reset operations, classical control and error-correction cycles should be included when the purpose is engineering estimation. Omitting them can make a theoretical algorithm appear substantially cheaper than its implementation.

6. Compilation and connectivity

A compiler transforms a logical circuit into instructions accepted by a target backend. Typical stages include gate unrolling, optimization, qubit mapping, routing, scheduling and measurement handling.

Gate decomposition

A hardware may support a native gate set such as single-qubit rotations and a particular entangling gate. An abstract controlled operation may therefore be decomposed into several native operations. Decomposition can increase gate count and depth, and different decompositions may have different error profiles.

Connectivity and routing

Real processors generally do not allow every qubit to interact directly. If a two-qubit gate is requested between nonadjacent qubits, the compiler may insert SWAP gates. A SWAP exchanges the states of two qubits and is often decomposed into three entangling gates, although the exact cost depends on the native instruction set.

Routing creates a trade-off: a mapping that minimizes initial distance may be poor later in the circuit. Compiler optimization should therefore be assessed using the final compiled circuit, not only the original logical circuit.

Optimization and reproducibility

Compiler optimization may cancel inverse gates, merge rotations, reorder commuting operations or choose alternative decompositions. Compilation settings, SDK versions, backend calibration data and random seeds can affect the result. Reproducible experiments should record all of them.

7. Noise, error mitigation and fault tolerance

Main noise mechanisms

Coherent errors arise from systematic over- or under-rotations and unwanted interactions. Stochastic errors include random Pauli-like faults. Relaxation and dephasing reduce coherence over time. Measurement error causes the reported classical bit to differ from the pre-measurement state. Crosstalk occurs when operating one qubit affects another.

Errors accumulate with circuit duration and operation count, but accumulation is not always a simple linear process. Correlations, cancellation, dynamical effects and compiler choices can change the result.

Error mitigation

Error mitigation attempts to improve estimates without fully correcting every error. Methods include:

• measurement-error mitigation using a calibrated assignment matrix;
• zero-noise extrapolation by executing noise-scaled circuits;
• probabilistic error cancellation using calibrated error models; and
• symmetry verification, which rejects or corrects results violating known invariants.

Mitigation does not create a fault-tolerant computation. It may increase shot requirements, amplify statistical variance, rely on an imperfect noise model and produce biased estimates when assumptions fail. Claims of improvement should therefore compare uncertainty as well as the central estimate.

Fault tolerance

Fault-tolerant quantum computing encodes logical information into an error-correcting code and performs operations in a way that suppresses logical errors below a threshold, provided physical error rates and other conditions are suitable. The threshold is architecture- and noise-model-dependent; it is not a universal number. Fault-tolerant resource estimation must include code distance, syndrome-extraction circuits, logical gate constructions, decoding and physical-qubit overhead.

8. A practical benchmarking workflow

A defensible experiment can follow this sequence:

1. Specify the claim. Define whether the goal is correctness, speed, fidelity, expectation estimation or noise robustness.
2. Create a reference. Use analytical calculations, an exact simulator or a trusted classical computation where feasible.
3. Implement the logical circuit. Keep algorithm code separate from backend-specific code.
4. Test small instances. Check basis states, symmetries and inverse operations.
5. Compile and inspect. Record width, depth, gate counts, native operations and routing overhead.
6. Run ideal and noisy simulations. Separate algorithmic error from modelled hardware error.
7. Execute repeated trials. Use a stated shot count and record calibration information.
8. Estimate uncertainty. Report confidence intervals or standard errors, not only point estimates.
9. Compare metrics. Examine accuracy, two-qubit count, depth, runtime and shot cost together.
10. Document reproducibility. Record code version, SDK version, backend, compiler options, seed, date and data-processing procedure.

A useful result table might include logical depth, compiled depth, logical and physical qubit counts, two-qubit gates, shots, observed success probability and uncertainty.

9. Illustrative case: verifying a three-qubit teleportation circuit

Background

Quantum teleportation transfers an unknown single-qubit state using shared entanglement, two classical bits and a conditional correction. It does not transmit matter or classical information faster than light.

Problem

A laboratory team implements teleportation and observes a lower-than-expected probability that the receiver reproduces the input state. The team must determine whether the problem is a coding error, compilation overhead, noise or insufficient sampling.

Analysis and approach

The team first tests the circuit on the basis states |0⟩ and |1⟩, followed by |+⟩ and |−⟩. For each input, it runs an ideal state-vector simulation and records the expected receiver distribution. It then runs a shot-based ideal simulation with 4,000 shots. For a success probability near 0.9, the approximate standard deviation is

Thus random sampling alone would typically produce variation of roughly 0.5 percentage points in one standard deviation; a much larger discrepancy requires investigation.

The logical circuit is transpiled to a device whose coupling map does not directly connect all three qubits. The compiler inserts four SWAP-equivalent routing operations, increasing the two-qubit gate count from 4 to 16 and increasing depth from 9 to 31 layers. The team compares this result with an alternative initial qubit layout, reducing the compiled two-qubit count to 11 and depth to 23.

The best layout is then tested under a calibrated noisy simulator and on hardware. Measurement-error mitigation improves the estimated success rate from 0.78 to 0.84, but the uncertainty also increases because the mitigation procedure uses a statistical inverse. The result remains below the ideal value, consistent with residual two-qubit and decoherence errors.

Outcome

The original discrepancy has multiple causes. The circuit was logically correct, but the first qubit layout produced unnecessary routing. Hardware noise caused the remaining loss of fidelity, while finite shots contributed only a smaller uncertainty. The final report distinguishes ideal correctness, compiled resource cost and physical performance.

Learning points

1. A logically correct circuit can be inefficient after compilation.
2. Routing overhead should be measured in the physical circuit.
3. Shot noise and hardware noise must not be confused.
4. Error mitigation can improve bias while increasing variance.
5. Verification should use several input states and independent references.

10. Best practices and limitations

Use the smallest circuit that tests the intended property, but do not infer scalability from a tiny instance without analysis. Prefer independent validation paths: for example, compare an SDK simulator with a hand-derived probability distribution. Report both logical and compiled resources. Separate statistical uncertainty from systematic error. Treat simulator noise models as hypotheses rather than exact descriptions of hardware.

Resource estimates are conditional. They depend on gate set, connectivity, compiler, calibration, encoding, error model, confidence requirement and problem size. A single number labelled “cost” is therefore inadequate. Good engineering reports provide assumptions and ranges where appropriate.

Ethical and governance considerations also matter. Benchmark claims should not selectively report favourable circuits or hide failed runs. Reproducible data and transparent uncertainty protect against exaggerated claims about quantum advantage. Proprietary hardware data must be handled according to access and privacy agreements, while educational experiments should avoid presenting simulated results as evidence of real-device performance.

Chapter Summary

Implementation turns an abstract quantum algorithm into a reproducible computational experiment. State-vector, shot-based and noisy simulators answer different questions and have different limitations. Verification combines analytical references, structural checks, property-based tests and statistical comparison. Width, depth, gate count, two-qubit operations, shots, runtime and fidelity describe different aspects of cost and quality.

Logical resources belong to the ideal algorithm, whereas physical resources include native gates, connectivity, routing, calibration, measurement, control and—under fault tolerance—error-correction overhead. Compilation can substantially change circuit depth and gate count. Noise reduces performance through gate, decoherence, crosstalk and readout errors. Error mitigation may reduce bias but does not replace fault tolerance and can increase variance. Reliable quantum software practice requires explicit assumptions, uncertainty estimates, compiled-circuit inspection and reproducible records.

Key Terms

Logical circuit: An abstract circuit expressed in ideal algorithmic operations.

Physical circuit: A circuit expressed in the native operations and connectivity of a device.

Quantum SDK: A software framework for constructing, compiling and executing quantum programs.

State-vector simulation: Numerical simulation that stores amplitudes of a pure quantum state.

Shot: One repeated execution and measurement of a circuit.

Circuit width: Number of qubits used by a circuit.

Circuit depth: Number of sequential operation layers on the critical path.

Native gate: An instruction directly supported by a target backend.

Transpilation: Compilation of a circuit into a backend-compatible form.

Routing: Insertion of operations needed to satisfy hardware connectivity.

Fidelity: A measure of agreement between quantum states or distributions.

Total variation distance: A distributional distance equal to half the sum of absolute probability differences.

Coherent error: A systematic error such as an incorrect rotation angle.

Readout error: Incorrect classical reporting of a measured quantum state.

Error mitigation: Techniques that improve estimates without complete error correction.

Fault tolerance: Reliable computation using error-correcting encodings and protected operations.

Ancilla: An auxiliary qubit used during computation.

Statistical uncertainty: Variation caused by finite sampling.

Connectivity map: The set of physical qubit pairs supporting direct interactions.

Reproducibility: Ability to repeat an experiment and obtain comparable results using documented conditions.

Review Questions

5 Short Answer Questions

1. What is the difference between logical and physical circuit depth?
2. Why does increasing the number of shots reduce statistical error only as approximately 1/√N?
3. Name two causes of routing overhead during compilation.
4. What information is represented by a state vector?
5. Why should a noisy simulator not automatically be treated as a faithful hardware model?

5 Long Answer Questions

1. Explain a complete SDK workflow from circuit construction to result validation.
2. Compare state-vector, shot-based and noisy simulation, including an appropriate use for each.
3. Discuss how gate decomposition and limited connectivity affect physical resource estimates.
4. Explain fidelity, total variation distance and expectation-value uncertainty as verification metrics.
5. Describe the differences between error mitigation and fault tolerance.

3 Analytical / Application Questions

1. A circuit uses 2,000 shots and has an estimated success probability of 0.8. Calculate the binomial standard deviation of the estimated success frequency and explain its meaning.
2. A logical circuit has 20 two-qubit gates, but compilation inserts 15 SWAP gates, each decomposed into three two-qubit operations. Calculate the compiled two-qubit gate count and discuss why it may be a more relevant hardware metric.
3. Design a benchmarking plan for comparing two qubit layouts. Specify the measurements, controls, uncertainty reporting and criteria you would use to choose between them.

Multiple Choice Questions with Answers

Question 1

Which metric counts the maximum number of qubits that must be available simultaneously?

A. Circuit width

B. Circuit depth

C. Shot count

D. Fidelity

Correct Answer: A. Circuit width

Question 2

For an ideal probability p estimated from N independent shots, which expression gives the binomial standard deviation?

A. p/N

B. √[p(1 − p)/N]

C. N√p

D. √[N/p]

Correct Answer: B. √[p(1 − p)/N]

Question 3

What is the main purpose of routing in quantum compilation?

A. To increase the number of measurement shots

B. To satisfy the processor’s qubit-connectivity constraints

C. To convert probabilities into amplitudes

D. To remove all statistical uncertainty

Correct Answer: B. To satisfy the processor’s qubit-connectivity constraints

Question 4

For two pure states, which expression defines state fidelity?

A. |⟨ψ|φ⟩|

B. |⟨ψ|φ⟩|²

C. ⟨ψ|ψ⟩ + ⟨φ|φ⟩

D. 1 − |⟨ψ|φ⟩|²

Correct Answer: B. |⟨ψ|φ⟩|²

Question 5

A state-vector simulator using 16 bytes per complex amplitude requires approximately how much memory for 30 qubits, ignoring overhead?

A. 16 MiB

B. 1 GiB

C. 16 GiB

D. 30 GiB

Correct Answer: C. 16 GiB

Question 6

Which statement best distinguishes error mitigation from fault tolerance?

A. Mitigation always eliminates errors completely

B. Fault tolerance uses error-correcting encoding, whereas mitigation improves estimates without complete correction

C. Mitigation applies only to classical computers

D. Fault tolerance requires no additional physical resources

Correct Answer: B. Fault tolerance uses error-correcting encoding, whereas mitigation improves estimates without complete correction

Question 7

Why can two circuits with the same gate count have different execution times?

A. Depth and gate durations may differ

B. Gate count determines time uniquely

C. Shots have no effect on execution

D. Qubits cannot operate in parallel

Correct Answer: A. Depth and gate durations may differ

Question 8

Which practice most directly supports reproducibility?

A. Reporting only the best observed result

B. Hiding compiler settings

C. Recording the SDK version, backend, seed and shot count

D. Using a different circuit for every repetition

Correct Answer: C. Recording the SDK version, backend, seed and shot count

Question 9

A success probability is estimated as 0.9 from 4,000 shots. What is the approximate binomial standard deviation?

A. 0.00047

B. 0.0047

C. 0.047

D. 0.47

Correct Answer: B. 0.0047

Question 10

What does total variation distance equal for two discrete distributions p and q?

A. ∑ₓ p(x)q(x)

B. 1/2 ∑ₓ |p(x) − q(x)|

C. ∑ₓ [p(x) + q(x)]

D. |p(0) − q(0)| only

Correct Answer: B. 1/2 ∑ₓ |p(x) − q(x)|