Quantum Computing and Programming Foundations

Introduction

Quantum computing is a method of information processing based on the laws of quantum mechanics. Classical computers represent information with bits that are either 0 or 1. Quantum computers use quantum bits, or qubits, whose physical states can exhibit superposition, interference, and entanglement. These properties do not make quantum computers universally faster. Rather, they provide a different computational resource that can be valuable for particular mathematical, scientific, and optimisation problems.

For programmers, quantum computing requires a shift in perspective. A quantum program does not usually prescribe a sequence of definite values in the same way as a classical program. Instead, it prepares and transforms probability amplitudes and finally obtains classical measurement results. Programming therefore involves state preparation, reversible operations, measurement, probability, and careful management of noise.

This chapter establishes the conceptual vocabulary required for later study of quantum circuits, programming frameworks, and simulation. It also distinguishes quantum computing from classical and hybrid computing and explains why identifying a suitable problem is as important as knowing how to build a quantum circuit.

Learning Objectives

After studying this chapter, you should be able to:

1. Define fundamental quantum-computing terminology.
2. Describe the historical development of quantum information processing.
3. Compare classical, quantum, and hybrid computation.
4. Explain qubits, superposition, measurement, interference, and entanglement.
5. Represent a single-qubit state using probability amplitudes.
6. Identify problem characteristics that may benefit, or may not benefit, from quantum approaches.
7. Explain practical limitations of current quantum hardware and simulation.
8. Evaluate a simple application using appropriate quantum-computing criteria.

1. From Classical Information to Quantum Information

Classical computation

A classical computer stores and processes bits. A bit has one of two logical values, conventionally written 0 and 1. Physical implementations may use voltage ranges, transistor states, magnetic orientations, or optical signals, but the abstract information model is binary.

A classical register containing n bits can represent one definite value among 2ⁿ possible bit strings at any instant. For example, a three-bit register can hold one of 000, 001, 010, ..., 111. A classical probabilistic computer may assign probabilities to these strings, but a single ordinary execution still samples or follows classical states; it does not create quantum amplitudes with quantum interference.

Classical logic gates include NOT, AND, OR, and XOR. Most elementary gates are irreversible: knowing the output of an AND gate does not generally reveal both inputs. Quantum computation, by contrast, uses reversible transformations on quantum states. Reversibility is essential because isolated quantum evolution is represented mathematically by a unitary operation.

Quantum computation

A quantum computer uses physical systems whose states obey quantum mechanics. Candidate systems include superconducting circuits, trapped ions, neutral atoms, photons, semiconductor spin qubits, and other platforms. The implementation differs, but the programming concepts are shared:

• a qubit is the basic information unit;
• gates transform qubit states;
• measurement converts quantum information into classical outcomes;
• algorithms exploit amplitude manipulation, interference, and sometimes entanglement.

A quantum computer does not simply try every possible answer simultaneously and read all answers at once. Measurement yields limited classical information. A successful quantum algorithm must arrange amplitudes so that desirable answers are more likely and undesirable answers cancel or become less likely.

2. Historical Development

The foundations of quantum theory emerged in the early twentieth century through work on energy quantisation, wave–particle duality, and the mathematical description of microscopic systems. In the 1980s, researchers began to ask whether quantum systems could be used as computational devices rather than merely simulated by classical machines.

Important milestones include:

• 1980–1982: Paul Benioff and Richard Feynman developed influential models of quantum computation and quantum simulation. Feynman argued that classical machines could simulate quantum systems inefficiently in important cases.
• 1985: David Deutsch described a general-purpose quantum computer model based on quantum gates.
• 1990s: Quantum error correction showed theoretically that noise need not make large-scale quantum computation impossible, provided physical error rates and control conditions are sufficiently good.
• 1994: Peter Shor introduced a polynomial-time quantum algorithm for integer factoring and the discrete logarithm problem, demonstrating possible consequences for some public-key cryptography.
• 1996: Lov Grover introduced a quantum search algorithm offering a quadratic speedup for unstructured search.
• Late 1990s onward: Experimental platforms began implementing small quantum circuits and demonstrating entanglement control.
• 2010s and 2020s: Cloud-accessible quantum processors, software development kits, error-mitigation methods, and research into fault-tolerant architectures expanded substantially.

Quantum computing remains an active engineering field. Demonstrating a small circuit is different from achieving reliable, scalable, fault-tolerant computation. The latter requires enormous improvements in coherence, control, fabrication, calibration, and error correction.

3. Essential Quantum Terminology

A quantum state is the mathematical description of a quantum system. A qubit is a two-level quantum system used to encode quantum information. A quantum register is a collection of qubits. A quantum gate is a controlled physical or mathematical operation that transforms a quantum state.

A circuit is an ordered arrangement of gates, measurements, and sometimes classical control. A shot is one execution of a circuit followed by measurement. Repeating a circuit many times produces a distribution of outcomes called a measurement histogram.

Coherence is the preservation of phase relationships needed for quantum interference. Decoherence is the loss of quantum coherence through interaction with the environment. Noise includes all unwanted errors in state preparation, gate operations, measurement, and control.

A unitary operation preserves the total probability of a quantum state and is reversible. Fidelity measures how closely an implemented state or operation matches the intended one; the exact definition depends on the context. Error mitigation attempts to reduce the effect of errors without fully correcting every error. Quantum error correction encodes logical information into multiple physical qubits so that errors can be detected and corrected.

A logical qubit is an error-corrected qubit encoded using physical qubits. A physical qubit is the actual device-level quantum system. Current processors generally contain noisy physical qubits, whereas large-scale fault-tolerant applications require logical qubits with sufficiently low effective error rates.

4. The Qubit and Its Mathematical Representation

The classical states of a bit are written 0 and 1. The corresponding computational basis states of a qubit are written |0⟩ and |1⟩. A general pure single-qubit state is

where α and β are complex probability amplitudes. The normalisation condition is

Here, |α|² is the probability of measuring 0, and |β|² is the probability of measuring 1 in the computational basis. The vertical bars denote complex magnitude. The amplitudes themselves are not probabilities and may be negative or complex. Their relative phase can affect later interference.

The state |0⟩ is represented by α = 1 and β = 0; |1⟩ is represented by α = 0 and β = 1. A balanced state is

For this state, measurement in the computational basis gives 0 and 1 with equal probability, 1/2 each. The state

has the same computational-basis measurement probabilities, but it has a different relative phase. Consequently, |+⟩ and |−⟩ can behave differently when further gates are applied.

Worked example: measuring a qubit

Suppose a qubit is prepared as

The amplitudes are α = √3/2 and β = 1/2. The probabilities are

and

They sum to 1, as required. A single measurement produces either 0 or 1, not both. If the experiment is repeated many times with the same preparation, approximately 75% of outcomes are expected to be 0 and 25% to be 1, subject to statistical fluctuation and hardware noise.

5. Superposition, Phase, and Measurement

Superposition

Superposition means that a quantum state can be a linear combination of basis states. It does not mean that a measurement displays multiple classical answers simultaneously. Before measurement, amplitudes can be transformed by gates and can interfere. Measurement produces a classical outcome according to the relevant probabilities.

A common way to create superposition is the Hadamard gate, H. Its action on the computational basis is

The Hadamard operation is reversible because applying it twice returns the original state: H² = I, where I is the identity operation.

Phase

The phase of an amplitude is particularly important because probabilities depend on magnitude squared, whereas interference depends on relationships among amplitudes. A global phase multiplying the entire state does not change measurement statistics. A relative phase between components can change the result of subsequent operations.

For example, |+⟩ and |−⟩ both give equal probabilities when measured immediately in the computational basis. Applying H again gives

and

Thus, the phase difference becomes observable after the second Hadamard operation.

Measurement

Measurement is the process of extracting classical information from a quantum system. In the computational basis, a qubit in state α|0⟩ + β|1⟩ gives 0 with probability |α|² and 1 with probability |β|². For an ideal projective measurement, the state after the outcome is consistent with the observed basis state. This is often described as state collapse.

Measurement is basis-dependent. A state that is definite in one basis may be a superposition in another. In programming practice, the chosen measurement basis is part of the algorithm design.

6. Interference

Interference is the addition and cancellation of probability amplitudes. Amplitudes can reinforce one another constructively or cancel destructively. Quantum algorithms use gates to guide interference toward useful outcomes.

Consider the sequence H–H applied to |0⟩. The first H creates equal amplitudes. The second H recombines them so that the |1⟩ amplitude cancels and the |0⟩ amplitude is reinforced, returning |0⟩. This is not a contradiction of superposition; it demonstrates that intermediate amplitudes are transformed before measurement.

Interference is one reason quantum algorithms are not simply parallel classical computation. An algorithm must encode a problem into amplitudes and then arrange a transformation that changes the measurement distribution in a useful, verifiable way.

7. Entanglement

Entanglement is a form of non-classical correlation between quantum systems. A two-qubit state is entangled if it cannot be written as a product of two single-qubit states. One important entangled state is the Bell state

Measuring either qubit in the computational basis gives 0 or 1 with equal probability, but the results are perfectly correlated: if the first result is 0, the second is 0; if the first is 1, the second is 1.

A simple preparation sequence is:

1. Start with |00⟩.
2. Apply H to the first qubit, producing (|00⟩ + |10⟩)/√2, subject to the ordering convention used for the register.
3. Apply a controlled-NOT gate with the first qubit as control and the second as target.
4. Obtain the Bell state (|00⟩ + |11⟩)/√2.

The precise displayed ordering of basis states depends on the software convention for which qubit is written first. The physical correlation does not depend on that notation choice.

Entanglement is not a method for sending usable information faster than light. It produces correlations that cannot generally be explained by assigning independent classical states to the separated systems, but communication still requires an ordinary classical channel.

8. Quantum Gates and Circuits

Quantum gates are reversible transformations. Common single-qubit gates include:

The Pauli-X gate acts as X|0⟩ = |1⟩ and X|1⟩ = |0⟩. The Pauli-Z gate acts as Z|0⟩ = |0⟩ and Z|1⟩ = −|1⟩.

Two-qubit gates include controlled-NOT, controlled-phase, and swap operations. The controlled-NOT flips the target qubit when the control qubit is |1⟩. Multi-qubit gates can create entanglement and implement more complex transformations.

A circuit has a temporal direction, usually represented from left to right. Gates are applied in sequence, and measurements normally occur at the end, although intermediate measurement and classical control are possible. A simulator represents the state mathematically; hardware implements operations physically and introduces errors.

9. Classical, Quantum, and Hybrid Computation

Classical computation

Classical systems are excellent for general-purpose control, data storage, web services, numerical simulation, and most business applications. They are mature, inexpensive, scalable, and comparatively robust. Classical processors use deterministic or probabilistic algorithms, often with parallelism through multiple cores, graphics processors, or distributed systems.

Quantum computation

Quantum computation uses quantum states and operations to solve selected problems. Its strengths are algorithm-dependent. The quantum device is usually controlled by classical electronics and cannot operate as an isolated replacement for every classical component.

Hybrid computation

A hybrid system combines classical and quantum processing. A classical computer may prepare input data, compile a circuit, send it to a quantum processor, collect measurements, update parameters, and repeat. This model is central to near-term variational algorithms.

A generic hybrid loop is:

1. Choose classical parameters θ.
2. Construct and execute a parameterised quantum circuit.
3. Measure the circuit repeatedly.
4. Estimate a cost function C(θ).
5. Use a classical optimiser to update θ.
6. Stop when a termination condition is reached.

The cost estimate is statistical. If an observable has outcomes with variance σ² and is estimated from N independent shots, the standard error of the sample mean is approximately σ/√N. This relationship assumes independent, identically distributed measurements and is a sampling estimate, not a guarantee about hardware error.

10. Which Problems May Benefit from Quantum Computing?

Quantum advantage is not determined by whether a problem sounds complex. It depends on mathematical structure, input and output requirements, available algorithms, implementation costs, and comparison with the best classical methods.

Potentially promising categories include:

• Quantum-system simulation: Molecules, materials, and chemical reactions are naturally quantum mechanical. Quantum simulation may represent their states more directly than classical methods for some regimes.
• Integer factoring and discrete logarithms: Shor’s algorithm provides a major theoretical speedup on a sufficiently large, fault-tolerant quantum computer. It is not currently practical on ordinary noisy devices.
• Unstructured search: Grover’s algorithm provides a quadratic query speedup, changing a search scale from approximately N evaluations to approximately √N oracle evaluations under its model. The oracle-construction and data-loading costs remain important.
• Certain linear-algebra and sampling tasks: Some algorithms offer theoretical improvements under restrictive data-access and precision assumptions.
• Combinatorial optimisation: Quantum approximate optimisation and annealing approaches are actively researched, but broad, consistent practical advantage over advanced classical optimisation has not been established.
• Machine learning subroutines: Quantum machine learning is a research area, but data encoding, training, noise, and classical baselines often limit claimed advantages.

Problems may not benefit when they involve simple sequential logic, small data sets, frequent random memory access, low-latency control, or input/output volumes that dominate computation. A quantum processor is also unlikely to help merely because a classical program is slow; the slowdown may arise from poor implementation, data movement, an unsuitable algorithm, or insufficient classical hardware.

A responsible feasibility assessment asks:

1. Is there a known quantum algorithm for the problem?
2. What speedup is theoretically established, and under what assumptions?
3. How are classical data encoded into quantum states?
4. How many qubits, gates, and measurements are required?
5. Can present hardware execute the circuit with useful accuracy?
6. Is the quantum result better than the best classical baseline after all overheads?
7. Can the result be verified and interpreted?

11. Simulation and Programming Foundations

A quantum simulator calculates the expected behaviour of a circuit on classical hardware. For an ideal pure state of n qubits, a state-vector simulator generally stores 2ⁿ complex amplitudes. If each complex amplitude uses b bytes, the amplitude storage alone is approximately b × 2ⁿ bytes, excluding overhead. This exponential scaling explains why classical simulation becomes difficult as the qubit count grows.

Other simulation methods include stabiliser simulation for restricted gate sets, tensor-network methods for circuits with suitable structure, density-matrix simulation for mixed states, and noise models that approximate hardware imperfections. No single simulator is best for every circuit.

Good quantum programming practice includes:

• specify the qubit ordering convention;
• distinguish state amplitudes from measurement frequencies;
• normalise and validate input states;
• use unit tests for small circuits with known results;
• compare simulator results with analytical predictions;
• run enough shots to estimate probabilities responsibly;
• track circuit depth, gate count, and two-qubit-gate count;
• document noise assumptions and backend characteristics;
• use classical baselines and independent verification.

12. Illustrative Case: Molecular-Energy Estimation

Background

This fictional case illustrates a realistic educational workflow rather than a claim of current commercial advantage. A university chemistry group wants to estimate the ground-state energy of a small molecule to compare candidate catalyst designs.

Problem

Classical electronic-structure methods can be accurate but may become expensive as molecular size and required precision increase. The group asks whether a near-term quantum processor can provide useful estimates.

Analysis

The problem is a candidate for quantum investigation because molecular states are quantum mechanical. However, the full workflow includes basis selection, Hamiltonian construction, mapping fermionic operators to qubits, circuit design, parameter optimisation, measurement, error mitigation, and comparison with trusted classical calculations.

The group chooses a variational approach. A parameterised circuit prepares a trial state |ψ(θ)⟩. The expected energy is estimated from the Hamiltonian H:

Here, θ is the vector of circuit parameters, H is the molecular Hamiltonian expressed in an appropriate qubit representation, and E(θ) is the expected energy. The method seeks parameters that minimise E(θ), subject to the accuracy of the state preparation and measurement process.

Approach and solution

The classical computer constructs H and selects θ. The quantum processor executes the circuit repeatedly to estimate the expectation values of the Hamiltonian’s terms. A classical optimiser updates θ. The group first validates the circuit on a simulator and compares it with a small exact diagonalisation result. It then executes the circuit on hardware using measurement-error mitigation and records uncertainty.

Outcome

The hardware estimate agrees qualitatively with the reference but has greater error than the simulator because of gate noise, finite sampling, and limited circuit depth. The result is useful as a controlled training exercise and as an engineering benchmark, but it does not yet demonstrate a practical advantage.

Learning points

The case demonstrates that a quantum application is a complete computational workflow, not merely a circuit. It also shows why classical preprocessing, classical optimisation, verification, error analysis, and honest comparison are essential. A quantum method can be scientifically valuable even when it does not outperform classical computation, provided its assumptions and results are evaluated rigorously.

13. Limitations, Ethics, and Governance

Current quantum devices face limited coherence times, imperfect gates, measurement errors, crosstalk, calibration drift, restricted connectivity, and limited qubit counts. Error correction requires additional physical qubits and engineering resources. Claims of “quantum advantage” should therefore identify the benchmark, hardware conditions, error model, classical competitor, and total workflow cost.

Security is a major governance issue. A sufficiently capable fault-tolerant quantum computer could threaten widely used public-key systems based on factoring or discrete logarithms. Organisations should plan migration toward post-quantum cryptography rather than assuming that quantum machines are either harmless or immediately capable of breaking existing systems.

Other responsible-practice issues include protecting confidential data submitted to cloud quantum services, reporting failed experiments as well as successful ones, avoiding exaggerated performance claims, and ensuring reproducibility through circuit specifications, software versions, seeds where relevant, backend information, and shot counts.

Quantum computing also has environmental and economic costs. Cryogenic systems, control electronics, fabrication, and specialised facilities require substantial resources. A technically impressive quantum solution is not automatically the most sustainable or cost-effective solution.

14. Contemporary Direction

The field is moving from demonstrations of isolated quantum effects toward scalable architectures and useful, verifiable workloads. Important research directions include fault-tolerant logical qubits, improved quantum error-correcting codes, modular networking, error mitigation, compilation, quantum control, benchmarking, and domain-specific algorithms.

Near-term work is predominantly hybrid. Classical processors manage data and optimisation while quantum processors perform carefully selected subroutines. Students entering the field therefore need both quantum concepts and conventional programming skills, including linear algebra, probability, software testing, numerical methods, and performance evaluation.

Chapter Summary

Quantum computing processes information using quantum states rather than only definite classical bit values. A qubit may be written as α|0⟩ + β|1⟩, with amplitudes satisfying |α|² + |β|² = 1. Measurement produces classical outcomes according to squared amplitude magnitudes. Superposition supplies a space of possible amplitudes; phase and interference allow amplitudes to reinforce or cancel; entanglement creates non-classical correlations between qubits.

Quantum gates are reversible transformations, and circuits combine gates with measurement. Classical computers remain superior for many routine, data-intensive, and low-latency tasks. Quantum processors are most promising where a suitable quantum algorithm exploits problem structure, particularly in quantum simulation and selected mathematical problems. Hybrid systems combine quantum circuits with classical optimisation and control.

Practical evaluation must include data encoding, circuit resources, noise, shot requirements, verification, classical baselines, and total cost. Present hardware is limited, and theoretical speedups do not automatically imply practical advantage. Responsible quantum programming therefore requires technical accuracy, transparent benchmarking, security awareness, and realistic claims.

Key Terms

Qubit: A two-level quantum information unit.

Quantum state: A mathematical description of a quantum system.

Probability amplitude: A complex coefficient whose squared magnitude determines measurement probability.

Superposition: A linear combination of possible basis states.

Phase: An amplitude property that influences interference.

Measurement: The process of obtaining classical information from a quantum state.

Interference: Reinforcement or cancellation of probability amplitudes.

Entanglement: Non-separable quantum correlation between systems.

Quantum gate: A reversible transformation applied to one or more qubits.

Quantum circuit: An ordered arrangement of quantum operations and measurements.

Unitary operation: A reversible, norm-preserving quantum transformation.

Coherence: Preservation of quantum phase relationships.

Decoherence: Loss of quantum coherence through environmental interaction.

Physical qubit: A hardware-level qubit.

Logical qubit: An error-corrected qubit encoded in physical qubits.

Quantum simulator: Software or hardware that models quantum-system behaviour.

Shot: One execution and measurement of a quantum circuit.

Error mitigation: Methods that reduce observed error without full error correction.

Hybrid computation: Coordinated classical and quantum processing.

Quantum advantage: Demonstrated superiority of a quantum approach for a defined task and benchmark.

Review Questions

Short Answer Questions

1. What distinguishes a qubit from a classical bit?
2. Why must the amplitudes of a normalised qubit satisfy |α|² + |β|² = 1?
3. What is the role of interference in a quantum algorithm?
4. Define entanglement and explain why it is not faster-than-light communication.
5. Give two reasons why a quantum simulator is useful to a quantum programmer.

Long Answer Questions

1. Explain superposition, phase, measurement, and interference using the states |+⟩ and |−⟩.
2. Compare classical, quantum, and hybrid computation in terms of information representation, processing, and practical applications.
3. Describe the historical development of quantum computing from quantum simulation proposals to current noisy processors.
4. Explain the preparation and significance of a Bell state.
5. Discuss the technical and governance limitations that must be considered before claiming quantum advantage.

Analytical / Application Questions

1. A qubit is prepared as (√3/2)|0⟩ + (1/2)|1⟩. Calculate the probabilities of the two computational-basis outcomes and explain what would be observed over many shots.
2. A company proposes using a quantum computer to speed up a small database lookup with frequent updates and strict millisecond response times. Evaluate whether this is a strong candidate for quantum computing and justify your conclusion.
3. Design a high-level hybrid workflow for estimating the ground-state energy of a small molecule. Identify the roles of the classical computer, quantum processor, measurement shots, optimisation, and verification.

Multiple Choice Questions with Answers

Question 1

Which statement best describes a qubit in a general pure state?

A. It must always have either the value 0 or the value 1 before measurement.

B. It can be represented as α|0⟩ + β|1⟩, with |α|² + |β|² = 1.

C. It stores two independent classical bits simultaneously.

D. It is defined only by its measurement result.

Correct Answer: B. It can be represented as α|0⟩ + β|1⟩, with |α|² + |β|² = 1.

Question 2

A qubit is prepared as (√3/2)|0⟩ + (1/2)|1⟩. What is the probability of measuring 1?

A. 1/4

B. 1/2

C. 3/4

D. 1

Correct Answer: A. 1/4

Question 3

What is the primary computational role of interference?

A. To duplicate classical information without measurement

B. To make every possible answer directly readable

C. To reinforce some amplitudes and cancel others

D. To eliminate the need for a classical computer

Correct Answer: C. To reinforce some amplitudes and cancel others

Question 4

Which state is an example of an entangled two-qubit state?

A. |0⟩

B. |1⟩

C. (|0⟩ + |1⟩)/√2

D. (|00⟩ + |11⟩)/√2

Correct Answer: D. (|00⟩ + |11⟩)/√2

Question 5

What happens when a computational-basis qubit is measured?

A. The result is always both 0 and 1.

B. A classical outcome is obtained according to the state’s probabilities.

C. The qubit becomes a classical processor.

D. Its amplitudes are automatically increased.

Correct Answer: B. A classical outcome is obtained according to the state’s probabilities.

Question 6

Which feature most directly distinguishes a hybrid quantum algorithm?

A. It uses no measurements.

B. It uses only reversible quantum gates and no classical computation.

C. A classical computer repeatedly controls or optimises quantum-circuit executions.

D. It stores all data permanently in qubits.

Correct Answer: C. A classical computer repeatedly controls or optimises quantum-circuit executions.

Question 7

Which problem has a well-known theoretical quantum algorithm with a quadratic speedup for unstructured search?

A. Grover’s search problem

B. A simple sorting task with no oracle

C. Routine text formatting

D. Classical file compression in every case

Correct Answer: A. Grover’s search problem

Question 8

Why can classical simulation of a general n-qubit state become difficult?

A. A state-vector representation generally requires amplitudes for 2ⁿ basis states.

B. Quantum states cannot be represented mathematically.

C. Classical computers cannot perform addition.

D. Every quantum gate requires a separate physical quantum processor.

Correct Answer: A. A state-vector representation generally requires amplitudes for 2ⁿ basis states.

Question 9

Which is a practical limitation of current quantum hardware?

A. Perfectly reliable gates at unlimited scale

B. Decoherence and gate or measurement errors

C. Inability to perform any reversible operation

D. Absence of probability in measurement

Correct Answer: B. Decoherence and gate or measurement errors

Question 10

What should be included in a credible claim of quantum advantage?

A. Only the number of qubits advertised by a vendor

B. A comparison with an appropriate classical baseline and the full workflow cost

C. A statement that quantum computers are faster for all problems

D. A measurement from one circuit execution

Correct Answer: B. A comparison with an appropriate classical baseline and the full workflow cost