Quantum Computers

Quantum Computers
QR code for this page

Lecture notes on qubits, superposition, interference, entanglement, measurement, Shor and Grover algorithms, quantum error correction, quantum machine learning, and post-quantum cryptography.

A quantum computer does not derive its power merely from the popular statement that a qubit can be “0 and 1 at the same time.” The deeper distinction is that computational states are represented by complex probability amplitudes and quantum operations can transform those amplitudes so that interference increases the probability of useful measurement outcomes.

Unit 1: Quantum Information Foundations and the Computation Model

Quantum-circuit analysis begins with the qubits' initial state and the chosen basis. Apply each gate in order to the state vector or density matrix, distinguishing premeasurement amplitudes from measurement probabilities. Ideal pure-state calculations do not represent hardware noise, so readout and gate errors require separate evaluation. Obtaining one measurement outcome does not make that outcome certain.

1.1. From Classical Bits to Qubits

Single-qubit pure state represented as a vector on the Bloch sphere with phase evolution
Bloch sphere and qubit state

A pure single-qubit state is

|ψ> = α|0> + β|1>

with

|α|² + |β|² = 1

Measurement in the computational basis returns 0 with probability |α|² and 1 with probability |β|².

For n qubits the state vector may contain 2^n complex amplitudes:

|ψ> = Σx αx|x>

This exponential state-space dimension does not mean that a quantum computer performs 2^n ordinary computations and then exposes all 2^n answers. A measurement does not reveal the entire state vector. A useful quantum algorithm must arrange amplitudes and phases so that interference makes the desired property observable with sufficiently high probability.

1.2. Superposition and Interference

Interference of two Hadamard gates where the amplitude of zero is one half plus one half and that of one is one half minus one half and the probability of zero with relative phase is cosine squared of phi over 2
Hadamard interference and Mach-Zehnder amplitudes

Applying a Hadamard gate to |0> gives

H|0> = (|0> + |1>) / √2

A measurement now yields either basis state with equal probability. This alone provides no computational advantage.

The important feature appears when amplitudes are recombined. Because amplitudes carry phase, paths can interfere constructively or destructively. Quantum algorithm design therefore uses unitary transformations to amplify useful outcomes and suppress unwanted ones.

The ideal evolution of a closed quantum system is represented by a unitary operator:

|ψ'> = U|ψ>
U†U = I

Common gates include the Pauli X, Y, and Z gates, Hadamard H, phase gates, and controlled multi-qubit operations such as CNOT.

1.3. Entanglement

Bell-state preparation with Hadamard and controlled-NOT followed by correlated measurements
Bell-state entanglement

Some multi-qubit states cannot be decomposed into independent states of their constituent qubits. A Bell state is

|Φ+> = (|00> + |11>) / √2

Entanglement creates correlations that are central to quantum information processing, error correction, teleportation, and quantum networking. It does not provide controllable faster-than-light communication.

1.4. Measurement and Classical Control

Single-qubit Bloch-sphere state and computational-basis measurement probabilities
Qubit measurement probabilities

Most gate-model systems are hybrid:

classical program
→ prepare quantum state
→ apply quantum circuit
→ measure
→ classical bits
→ classical post-processing

Scheduling, control electronics, error handling, orchestration, data management, and application logic remain largely classical. Quantum states are internal computational representations.

It is nevertheless incorrect to claim that every quantum computer can accept only classical bits as input. Quantum networks, sensors, and other quantum systems may provide quantum states directly.

1.5. Historical Motivation

One of the original motivations for quantum computing was the difficulty of simulating quantum physics on classical machines. Richard Feynman emphasized that the state space of a quantum system can grow exponentially when represented directly on a classical computer. David Deutsch later developed the model of a universal quantum computer.

This leads to an important principle: a controllable quantum system can represent the mathematics of another quantum system without explicitly storing every amplitude in a classical state vector.

1.6. Meaning of Quantum Speedup

Quantum computers do not accelerate every algorithm. Advantage is problem-dependent and must be described in a specific computational model.

Relevant metrics include:

asymptotic complexity
query complexity
circuit depth
logical-qubit count
state-preparation cost
measurement count
error-correction overhead
classical pre/post-processing
wall-clock latency

A better Big-O expression for the quantum kernel is not sufficient by itself to establish practical advantage.

1.6.1. Grover's Algorithm

Amplitude evolution in an eight-state Grover search showing amplification of the marked state over successive iterations
Grover amplitude amplification

For unstructured search among N candidates, classical black-box search requires O(N) queries in the worst case. Grover's algorithm reduces the quantum query complexity to

O(√N)

This is a quadratic, not exponential, speedup. Its mechanism is amplitude amplification: an oracle marks the target and repeated transformations increase the target state's amplitude before measurement.

1.6.2. Shor's Algorithm

For N 15 and base 7 the sequence 7 to the x mod 15 with period 4, the quantum Fourier spectrum with probability 1 over 4 at 0, 4, 8 and 12, and the gcd step giving 15 equal to 3 times 5
Shor period finding example

Shor's algorithm provides polynomial-time quantum algorithms for integer factorization and discrete logarithms. This directly affects cryptosystems whose security depends on these problems, including RSA, finite-field Diffie-Hellman, and elliptic-curve discrete-logarithm systems.

The theoretical algorithm should not be confused with present hardware capability. Breaking modern cryptographic keys requires a large fault-tolerant machine with enough logical qubits and a sufficiently low logical error rate.

1.7. What Quantum Computers Do Not Do

Quantum computation does not remove the boundary between computable and uncomputable problems. An uncomputable problem does not become computable merely because the hardware is quantum.

Nor is there a known result showing that all NP-complete problems can be solved in polynomial time on a quantum computer. BQP captures the standard class of decision problems efficiently solvable with bounded error on a quantum computer, but the exact relationship between major complexity classes remains a theoretical question.

1.8. State Preparation and Data Loading

Suppose a classical vector

x = (x1, x2, ..., xN)

is to be amplitude-encoded as

|x> = 1/||x|| Σi xi|i>

Preparing this state may itself be expensive. Algorithms that assume efficient oracles, QRAM, sparse access, or pre-existing quantum states must be evaluated together with the cost of realizing those assumptions.

A fast quantum kernel surrounded by expensive loading and extraction can lose its end-to-end advantage.

1.9. Output and Measurement Bottlenecks

A quantum state can compactly represent information that cannot be fully extracted in one measurement. Consequently, many useful quantum algorithms estimate an observable, expectation value, classification, sample, or global property rather than writing every component of a large vector into classical memory.

1.9.1. HHL as an Example

The Harrow-Hassidim-Lloyd algorithm addresses

Ax = b

under specific assumptions concerning sparsity, conditioning, state preparation, and access to A and b.

Its output is a quantum state related to the solution:

|x>

not a free classical listing of all components of x. If every component must be reconstructed classically, readout can consume much of the theoretical advantage.

1.10. Mixed States, Density Matrices, and Noise

A state vector is sufficient for an isolated pure state, but an engineering model of noisy hardware also needs mixed states. A density operator

ρ = Σ p_i |ψ_i><ψ_i|

represents a statistical mixture of quantum states. Pure states satisfy Tr(ρ²)=1; mixed states have Tr(ρ²)<1.

Noise is then modeled as a transformation of the density operator rather than as a simple perturbation of one amplitude vector. Bit-flip, phase-flip, depolarizing, amplitude-damping, and dephasing channels capture different physical error mechanisms. The exact channel parameters are hardware- and calibration-dependent.

This distinction matters because a circuit with a small gate count can still fail if coherence time, readout error, crosstalk, or correlated noise dominates the computation.

1.11. Quantum Fourier Transform

QFT circuit with Hadamard gates, controlled phase rotations, and output swaps
Quantum Fourier transform

The quantum Fourier transform maps amplitudes into a Fourier-like basis:

|x> -> 1/sqrt(N) Σ_y exp(2πixy/N)|y>.

Its circuit can be built from Hadamard and controlled-phase operations. The QFT is not useful merely because it resembles the classical FFT; its value appears when a quantum algorithm can encode a problem so that phase information becomes measurable after the transform. Phase estimation and Shor-type algorithms are canonical examples.

Circuit depth, connectivity, approximation thresholds, and noise can make the textbook QFT very different from a useful hardware implementation.

Unit 2: Quantum Algorithms, Hardware, and Fault Tolerance

Assessing a quantum algorithm requires an explicit oracle model, problem size, and success probability. Consider gate count, circuit depth, and repeated executions together; ideal query complexity is not hardware runtime. Fault-tolerance requirements and classical pre- and postprocessing costs must be included. Compare against an appropriate classical algorithm at the same accuracy target.

2.1. Quantum Simulation

Quantum simulation is one of the most natural application areas because molecular and many-body systems are themselves quantum mechanical.

Potential applications include:

  • molecular ground-state energies,
  • reaction mechanisms,
  • catalyst design,
  • battery chemistry,
  • magnetic materials,
  • superconducting systems,
  • strongly correlated quantum matter.

The goal is not to eliminate physical experiments. A realistic use is to reduce the experimental search space and model candidate systems more accurately before laboratory validation.

2.2. Optimization

Quantum annealing, QAOA, and other methods are investigated for combinatorial optimization. Difficult optimization does not automatically imply quantum advantage. Strong classical baselines—including mathematical programming, local search, approximation algorithms, and specialized heuristics—must be included in any meaningful comparison.

Gate-model quantum computing and quantum annealing are distinct computational models and should not be compared by physical-qubit count alone.

2.3. Quantum Hardware

A qubit is an information concept, not one physical implementation. Research platforms include:

  • superconducting circuits,
  • trapped ions,
  • neutral atoms,
  • photonic systems,
  • semiconductor spin qubits,
  • topological approaches.

Important engineering metrics include gate fidelity, readout fidelity, coherence time, gate latency, connectivity, crosstalk, reset time, control complexity, scalability, and logical error rate.

2.4. Decoherence, Physical Qubits, and Logical Qubits

Real qubits interact with their environment. Gate errors, readout errors, crosstalk, thermal noise, control imperfections, and decoherence limit circuit depth.

A physical qubit is a hardware quantum degree of freedom. A logical qubit is protected quantum information encoded across multiple physical qubits using quantum error correction.

The resource chain is therefore:

algorithm
→ logical qubits
→ logical gates
→ target logical error rate
→ error correction
→ physical qubits
→ physical operations
→ wall-clock execution time

A thousand physical qubits and a thousand high-quality logical qubits are radically different resources.

2.5. Quantum Error Correction and Fault Tolerance

Quantum error correction with encoding, syndrome extraction, and correction
Quantum error correction

The no-cloning theorem prevents an unknown arbitrary quantum state from being copied perfectly. Classical redundancy schemes therefore cannot be transferred directly to quantum information.

Quantum error correction encodes logical information into larger entangled states and measures error syndromes without directly measuring the protected logical state.

Fault tolerance extends this principle to computation performed with imperfect components. If physical error rates satisfy the requirements of a fault-tolerant architecture, logical error rates can in principle be suppressed enough to support long computations, at substantial resource cost.

2.6. NISQ Systems and Hybrid Algorithms

Current processors are often discussed as noisy intermediate-scale quantum systems. They have limited circuit depth and are not general large-scale fault-tolerant machines.

Hybrid algorithms use a classical optimizer around a parameterized quantum circuit:

choose θ classically
→ prepare |ψ(θ)>
→ run quantum circuit
→ measure cost
→ update θ classically
→ repeat

VQE and QAOA are prominent examples. Hybrid structure alone does not establish advantage; measurement overhead, optimization difficulty, noise, and classical alternatives remain decisive.

2.7. Surface-code Intuition and Logical Error Rates

Surface-code logical error rate against physical error rate and code distance with the threshold and qubit cost
Logical error scaling

Fault tolerance does not mean that a physical qubit becomes error-free. A logical qubit is encoded across many physical qubits so that repeated syndrome measurements can reveal likely error chains without directly measuring the protected logical state.

Surface codes are important because they use local stabilizer measurements on a two-dimensional layout and have comparatively high error thresholds. Their cost is substantial: one useful logical qubit can require many physical qubits, additional ancilla qubits, repeated syndrome cycles, classical decoding, and enough code distance to suppress the logical error rate below the application target.

Resource estimation must therefore distinguish physical qubits, logical qubits, logical gate count and depth, code distance, error-correction cycle time, non-Clifford resources, and target logical failure probability.

A claim about “qubit count” without these distinctions is not an engineering capacity estimate.

Unit 3: Cryptography, Post-Quantum Security, and Quantum Networks

3.1. Cryptographic Impact

The clearest long-term security impact concerns public-key cryptography.

A sufficiently capable fault-tolerant quantum computer running Shor's algorithm threatens:

RSA
finite-field DH
ECDH
DSA
ECDSA

This is a future-capability threat model, not a claim that present quantum computers can break modern production keys.

3.1.1. Harvest Now, Decrypt Later

Long-lived confidential traffic can be collected today and stored until future cryptanalytic capability becomes available:

capture encrypted data now
→ retain it
→ obtain future quantum capability
→ attack vulnerable key establishment
→ decrypt historical data

Migration urgency therefore depends on data confidentiality lifetime as well as hardware timelines.

3.1.2. Symmetric Cryptography and Grover

For an ideal k-bit key search, Grover reduces query complexity from approximately

2^k

to

2^(k/2)

This does not equal practical wall-clock attack cost. Reversible circuit implementation, logical resources, error correction, and oracle depth substantially affect real cost.

3.2. Post-Quantum Cryptography

Post-quantum cryptography runs on classical computers and uses schemes intended to resist known classical and quantum attacks.

NIST's first core PQC standards published in 2024 include:

FIPS 203 → ML-KEM
FIPS 204 → ML-DSA
FIPS 205 → SLH-DSA

Migration is a system-engineering problem involving PKI, certificates, TLS, VPNs, HSMs, firmware signing, key management, protocol sizes, performance, interoperability, and long-lived devices.

Crypto-agility—the ability to replace cryptographic mechanisms without redesigning the entire system—is therefore strategically important.

3.3. Post-Quantum Cryptography vs Quantum Cryptography

PQC and quantum cryptography are different.

PQC uses classical hardware with quantum-resistant mathematical constructions. Quantum Key Distribution uses quantum states and physical communication properties.

BB84 is a foundational QKD protocol. QKD still requires authenticated classical communication and specialized infrastructure; it is not a drop-in software replacement for ordinary Internet cryptography.

3.4. Quantum Networks and No-Cloning

Quantum networks aim to distribute quantum states or entanglement between nodes. Quantum teleportation transfers a quantum state using shared entanglement plus classical communication; it does not transmit usable information faster than light.

The no-cloning theorem also means that classical concepts such as arbitrary copying, replication, and fan-out cannot be applied directly to unknown quantum states.

3.5. Key Agreement and Data Lifetime under Quantum Threats

Post-quantum migration must distinguish Shor's implications for traditional public-key hardness from Grover's effect on generic symmetric-key search. Data that remains valuable for many years may be exposed to record-now/decrypt-later threats. Ephemeral key exchange, AEAD protection of stored data, and long-term verification of signatures therefore follow different migration paths.

ML-KEM is a key-encapsulation mechanism, whereas ML-DSA and SLH-DSA are signature schemes. A hybrid key schedule must define its combination context, transcript binding, failure handling, and the assumption under which each component contributes security. Cryptology covers the primitives and standards; this course evaluates realistic quantum-computing capabilities and limits.

Unit 4: Quantum Advantage, Measurement, and Application Areas

4.1. Quantum Computational Advantage

A demonstration that a quantum device outperforms known classical methods on a specific task does not imply superiority on general workloads. Classical simulation algorithms also improve, making quantum advantage a moving target.

Performance must be characterized using more than physical-qubit count:

logical qubits
gate fidelity
measurement fidelity
coherence
connectivity
circuit depth
logical error rate
execution time

4.2. Classical Simulation Limits

A full state-vector simulation requires 2^n complex amplitudes. With 16 bytes per complex double-precision amplitude, raw state storage is approximately:

30 qubits → 16 GiB
35 qubits → 512 GiB
40 qubits → 16 TiB
45 qubits → 512 TiB
50 qubits → 16 PiB

Yet qubit count alone does not determine simulation difficulty. Tensor networks, stabilizer methods, symmetry, sparsity, low entanglement, and approximation can make particular circuits much easier to simulate.

4.3. A Realistic Hybrid Architecture

A plausible long-term architecture is:

application
    |
classical CPU/GPU system
    |
    +-- data management
    +-- networking
    +-- control
    +-- classical computation
    |
    +-- QPU accelerator
          |
          +-- selected quantum subroutines

The QPU is therefore better understood as a specialized accelerator than as a universal replacement for classical computing.

4.4. End-to-End Quantum Advantage

A practical comparison should account for:

Ttotal =
    Tstate_preparation
  + Tclassical_preprocessing
  + Tquantum_execution
  + Terror_correction
  + Tmeasurement
  + Trepetitions
  + Tclassical_postprocessing
  + Tcommunication

Practical advantage requires the full quantum path to outperform the best relevant classical implementation at the target problem size and accuracy.

4.5. Application Areas

Promising research areas include quantum chemistry, materials, selected optimization problems, finance, energy, and drug-related molecular simulation. Their maturity and evidence levels differ substantially.

Quantum computing should therefore be evaluated problem by problem rather than through broad claims about “exponential speed.”

Unit 5: Misconceptions and Engineering Assessment

5.1. Common Misconceptions

  • A qubit is not simply two classical bits processed simultaneously.
  • n qubits do not provide free access to 2^n classical answers.
  • Quantum computers are not known to solve all NP-complete problems efficiently.
  • Present quantum computers cannot run Shor at the scale required to break modern RSA keys.
  • PQC does not require a quantum computer.
  • QKD and PQC are different technologies.
  • More physical qubits do not automatically mean more useful computational power.
  • Quantum hardware does not automatically make general-purpose AI training exponentially faster.

5.2. Engineering Checklist

Before adopting a quantum approach, determine:

  1. What is the exact problem and output requirement?
  2. Which quantum algorithm applies?
  3. What is the strongest classical baseline?
  4. What data-access assumptions are required?
  5. What is the state-preparation cost?
  6. What is the oracle cost?
  7. How many logical qubits and logical gates are required?
  8. What logical error rate is necessary?
  9. What physical error-correction overhead follows?
  10. How many measurements and repetitions are required?
  11. How is the result extracted?
  12. What classical pre/post-processing is required?
  13. What is the end-to-end latency and resource cost?
  14. At what problem size does any advantage appear?

Quantum computing is important not because it removes every computational limit, but because it demonstrates that computational complexity can depend on the physical and mathematical model used to perform computation.

5.3. Resource Estimation and Logical versus Physical Qubits

An algorithm requiring N qubits does not imply that N physical qubits are enough. Fault-tolerant computation can require many physical qubits per logical qubit depending on physical error rates and code distance.

Feasibility therefore depends on gate count, circuit depth, T-count/T-depth, connectivity, and error-correction overhead as well as asymptotic complexity.

Claims of quantum advantage should use a strong classical baseline under the same problem definition and error tolerance.

5.4. Scoping Claims of Quantum Advantage

Asymptotic quantum advantage does not automatically imply practical advantage on current hardware. Problem size, circuit depth, gate error rates, qubit connectivity, error-correction overhead, and classical pre/post-processing all contribute to total cost.

The classical baseline should be current and evaluated at the same error tolerance. Comparing against a weak classical method does not establish quantum advantage. Approximate methods on both sides should use the same solution-quality metric.

For NISQ experiments, record shot count, transpilation settings, device calibration time, and error-mitigation method. Without these details, identical circuits run on different days are not directly comparable.

Unit 6: Quantum Machine Learning and Quantum-Inspired Methods

6.1. Quantum Machine Learning

Machine learning and quantum algorithms overlap in linear algebra, optimization, sampling, and high-dimensional representations. Research includes quantum kernels, parameterized quantum circuits, quantum linear-algebra methods, sampling, and learning directly from quantum data.

The distinction between classical data and quantum data is fundamental. Classical text, images, audio, and tabular data must be encoded into a quantum system. Quantum experimental data may already exist in a form naturally processed by a quantum device.

Claims of speedup must therefore include the data-access model.

6.1.1. Large Language Models

Modern Transformer workloads are dominated by large tensor operations executed efficiently on GPUs and other classical accelerators. Replacing a matrix multiplication with a quantum subroutine does not automatically accelerate an LLM.

An end-to-end analysis must include model-state preparation, input encoding, nonlinear operations, intermediate-state use, gradients, optimization, measurement, and classical control.

The correct question is not “Will quantum computers make AI exponentially faster?” but:

Which specific subproblem, under which data-access and output requirements, can be solved at lower end-to-end cost with a quantum algorithm?

6.2. Quantum-Inspired Classical Algorithms

Quantum research can also improve classical algorithms. Ewin Tang's work on recommendation systems demonstrated that part of an apparent quantum advantage could be reproduced classically when a comparable data-access model was available.

This suggests a rigorous comparison process:

identify the claimed quantum advantage
→ identify the structural assumption producing it
→ ask whether that assumption is genuinely quantum
→ compare with the strongest classical algorithm

6.3. Variational Circuits and Measurement Cost

Parameter-shift gradient in a variational circuit with computed steps and state transitions
Parameter-shift gradient in a variational circuit

Many NISQ-era methods combine a parameterized quantum circuit with a classical optimizer:

θ → quantum circuit → measurement → loss → classical optimization → θ'

Estimating losses or gradients may require many circuit executions and measurements. Qubit count alone is therefore not a cost metric; shot count, circuit depth, noise, and classical optimization iterations matter together.

6.4. Use a Strong Classical Baseline

A quantum machine-learning result is not evidence of advantage if it is compared only with a weak classical baseline. Comparison should use strong classical kernel, linear-algebra, or sampling methods under comparable data-access and output-accuracy assumptions. End-to-end cost must include encoding and measurement.

Quantum AI is therefore not the default successor to current production AI infrastructure. It is an active research area seeking advantage for specific problem structures and access models.

6.5. Quantum-inspired Networks, Quantum Neural Networks, and low-rank Emulation

Three computational models should be distinguished: variational circuits using physical qubits and measurements; quantum-inspired tensor or probabilistic models running on classical hardware; and dequantized classical routines that reproduce selected quantum subroutines under specified data-access assumptions. The first depends on depth, shot count, and noise; the second on tensor rank, memory, and contraction cost; the third on sample-and-query access, conditioning, and the expense of constructing input data structures.

A dense 4×4×4×4 tensor has 256 scalars. Tensor-train cores with internal rank 2 may store only 48 scalars, but approximation error and actual runtime must still be measured. Such classical compression demonstrates neither physical entanglement nor quantum advantage. End-to-end benchmarks must include state preparation, optimization, measurement, inference, and a strong classical comparator.

Unit 7: Noise, Error Mitigation, and Experimental Verification

Quantum error correction and quantum error mitigation solve different problems. Error correction encodes logical information so that sufficiently long computations can suppress failures below an application target. Error mitigation usually aims to reduce bias in expectation values obtained from noisy hardware; it does not generally make the computation fault tolerant.

7.1. Mixed States and Density Matrices

Dephasing, purity, and the density matrix with computed steps and state transitions
Dephasing, purity, and the density matrix

A pure quantum state can be represented by a state vector |ψ⟩. When a system interacts with an environment, or when there is classical uncertainty over the prepared state, a single state vector is insufficient. A density matrix is then used:

ρ = Σ p(i) |ψ(i)><ψ(i)|

Tr(ρ)=1 expresses normalization. For a pure state, Tr(ρ²)=1; for a mixed state it is less than 1. Noise channels can be defined on density matrices, giving a common language for processes such as dephasing, amplitude damping, and depolarization.

7.2. Error Mitigation versus Error Correction

Zero-noise extrapolation trades bias for variance with computed steps and state transitions
Zero-noise extrapolation trades bias for variance

Mitigation can improve an estimator without encoding logical qubits, but it usually requires additional circuit executions, calibration data, and statistical overhead.

Zero-noise extrapolation runs related circuits at controlled effective noise levels and extrapolates the measured quantity toward a zero-noise limit. Probabilistic error cancellation reconstructs an ideal expectation value from weighted samples of noisy operations. Both approaches depend on assumptions about the noise model or how noise can be scaled.

7.3. Readout Error and Shot Statistics

Shot noise and readout-error correction with computed steps and state transitions
Shot noise and readout-error correction

A quantum circuit does not return the full probability distribution in one execution. Repeated measurements provide samples. With N shots, sampling uncertainty generally decreases on the order of 1/sqrt(N), with the exact variance depending on the measured probability.

A small difference between two experiments should therefore not be interpreted as an algorithmic improvement without accounting for sampling uncertainty and readout error. Calibration-based readout mitigation may reduce measurement bias, but calibration drift introduces another source of uncertainty.

7.4. Calibration Drift and Experiment Records

The same logical circuit can map to different physical qubits or experience different gate and readout error rates at different times. A reproducible experiment should record not only the source circuit but also transpilation settings, physical mapping, shot count, calibration time, and the mitigation method.

Techniques such as randomized benchmarking characterize average behavior of selected gate sets. They do not by themselves establish the end-to-end fidelity of a specific algorithm. Hardware metrics and application metrics must remain distinct.

7.5. Engineering Conclusion

Error mitigation is a statistical technique for extracting more useful estimates from noisy execution. It trades additional sampling and model assumptions for reduced bias and may increase variance. Fault-tolerant computation is a different resource problem involving logical qubits, repeated error-correction cycles, and application-level failure targets.

7.6. Defining Performance Metrics Correctly for Quantum Systems

The duration of an individual quantum gate does not describe an algorithm's end-to-end cost. Qubit preparation, calibration, circuit depth, shot count, readout error, and classical post-processing introduce distinct time components. Devices with similar gate times may also require different routing operations because of connectivity and error-rate constraints. Meaningful comparisons therefore report physical-device limits, solution fidelity, and total completion time together.

  • Separate preparation, control, measurement, and classical post-processing instead of citing only one gate/operation time.
  • Hold problem size and error-correction assumptions constant in throughput comparisons.
  • Show that the bottleneck in a hybrid classical-quantum workflow may not reside on the QPU.

References

  • Bennett, C. H.; Brassard, G. “Quantum Cryptography: Public Key Distribution and Coin Tossing.” Proceedings of the International Conference on Computers, Systems and Signal Processing, 1984; reprinted in Theoretical Computer Science, 560, 7-11, 2014. https://doi.org/10.1016/j.tcs.2014.05.025
  • Bernstein, E.; Vazirani, U. “Quantum Complexity Theory.” SIAM Journal on Computing, 26, 1411-1473, 1997. https://doi.org/10.1137/S0097539796300921
  • Biamonte, J. et al. “Quantum Machine Learning.” Nature, 549, 195-202, 2017. https://doi.org/10.1038/nature23474
  • Bravyi, S.; Sheldon, S.; Kandala, A.; McKay, D. C.; Gambetta, J. M. “Mitigating Measurement Errors in Multiqubit Experiments.” Physical Review A, 103, 042605, 2021. https://doi.org/10.1103/PhysRevA.103.042605
  • Brendan Gregg. Systems Performance: Enterprise and the Cloud. Pearson Education, 2014.
  • Deutsch, D. “Quantum Theory, the Church-Turing Principle and the Universal Quantum Computer.” Proceedings of the Royal Society A, 400, 97-117, 1985. https://doi.org/10.1098/rspa.1985.0070
  • Feynman, R. P. “Simulating Physics with Computers.” International Journal of Theoretical Physics, 21, 467-488, 1982. https://doi.org/10.1007/BF02650179
  • Grover, L. K. “A Fast Quantum Mechanical Algorithm for Database Search.” Proceedings of STOC, 212-219, 1996. https://doi.org/10.1145/237814.237866
  • Harrow, A. W.; Hassidim, A.; Lloyd, S. “Quantum Algorithm for Linear Systems of Equations.” Physical Review Letters, 103, 150502, 2009. https://doi.org/10.1103/PhysRevLett.103.150502
  • Huang, H. Y. et al. “Quantum Advantage in Learning from Experiments.” Science, 376, 1182-1186, 2022. https://doi.org/10.1126/science.abn7293
  • Kaku, M. Quantum Supremacy: How the Quantum Computer Revolution Will Change Everything. Doubleday, 2023.
  • Mor Harchol-Balter. Performance Modeling and Design of Computer Systems: Queueing Theory in Action. Cambridge University Press, 2013.
  • Nielsen, M. A.; Chuang, I. L. Quantum Computation and Quantum Information. Cambridge University Press.
  • NIST. FIPS 203: Module-Lattice-Based Key-Encapsulation Mechanism Standard. 2024. https://csrc.nist.gov/pubs/fips/203/final
  • NIST. FIPS 204: Module-Lattice-Based Digital Signature Standard. 2024. https://csrc.nist.gov/pubs/fips/204/final
  • NIST. FIPS 205: Stateless Hash-Based Digital Signature Standard. 2024. https://csrc.nist.gov/pubs/fips/205/final
  • NIST. Post-Quantum Cryptography Project. https://csrc.nist.gov/projects/post-quantum-cryptography
  • Preskill, J. “Quantum Computing in the NISQ Era and Beyond.” Quantum, 2, 79, 2018. https://doi.org/10.22331/q-2018-08-06-79
  • Shor, P. W. “Algorithms for Quantum Computation: Discrete Logarithms and Factoring.” Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994.
  • Shor, P. W. “Scheme for Reducing Decoherence in Quantum Computer Memory.” Physical Review A, 52, R2493, 1995. https://doi.org/10.1103/PhysRevA.52.R2493
  • Shor, P. W. “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer.” SIAM Journal on Computing, 26, 1484-1509, 1997. https://doi.org/10.1137/S0097539795293172
  • Tang, E. “A Quantum-Inspired Classical Algorithm for Recommendation Systems.” Proceedings of STOC, 2019. https://doi.org/10.1145/3313276.3316310
  • Temme, K.; Bravyi, S.; Gambetta, J. M. “Error Mitigation for Short-Depth Quantum Circuits.” Physical Review Letters, 119, 180509, 2017. https://doi.org/10.1103/PhysRevLett.119.180509
  • Wootters, W. K.; Zurek, W. H. “A Single Quantum Cannot Be Cloned.” Nature, 299, 802-803, 1982. https://doi.org/10.1038/299802a0
  • Moolchand Sharma, Nebojsa Bacanin, and Tarik Ahmed Rashid (eds.). Quantum-Inspired Neural Networks: Future Perspectives and Challenges. CRC Press, DOI: https://doi.org/10.1201/9781003682950 (supplied copyright page ©2027).
Contents