Mapping Problems to Quantum Algorithms

Introduction

Quantum computing is not a universal replacement for classical computing. Its value depends on whether a problem can be represented in a form that a quantum algorithm can exploit. The central professional skill is therefore problem mapping: translating a business or scientific task into a mathematical model, identifying its computational structure, and selecting a quantum algorithm whose assumptions match that structure.

A poorly formulated problem remains poorly formulated on a quantum computer. Conversely, a clear formulation can reveal whether the task is primarily a search, optimization, simulation, sampling, estimation, factoring, or linear-algebra problem. This chapter develops a practical framework for making that translation.

Learning Objectives

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

1. Classify computational problems as search, optimization, simulation, sampling, estimation, or linear-algebra tasks.
2. Express practical problems using variables, constraints, objective functions, or quantum states.
3. Relate problem structures to Grover’s algorithm, Shor’s algorithm, phase estimation, amplitude estimation, and related methods.
4. Distinguish a quantum speedup in query complexity from an end-to-end practical advantage.
5. Evaluate encoding, oracle, measurement, noise, data-loading, and verification requirements.
6. Select a suitable quantum approach for a small business or scientific case.

1. The Problem-Mapping Perspective

A computational problem normally contains five components:

• Inputs: data, parameters, or an initial physical state.
• Decision variables: unknown quantities to be selected or determined.
• Constraints: conditions that acceptable solutions must satisfy.
• Objective or output: what must be maximized, minimized, estimated, sampled, or measured.
• Resource model: available time, memory, queries, circuit depth, precision, and hardware.

Quantum algorithm selection should follow this sequence:

1. State the practical question in plain language.
2. Define the mathematical output precisely.
3. Identify the problem class.
4. Determine how data and variables will be encoded into qubits.
5. Identify the required oracle, Hamiltonian, circuit, or linear-system operator.
6. Estimate quantum and classical costs.
7. Define how results will be measured and validated.

A quantum algorithm is not simply selected because a problem is large. It is selected because the problem has exploitable structure and because the cost of constructing and interpreting the quantum computation is acceptable.

2. Core Problem Classes

2.1 Search and decision

A search problem asks for an input satisfying a condition. Let the candidate set be {0, 1, …, N − 1}, and let f(x) be a Boolean predicate. The goal is to find x such that f(x) = 1. A decision version asks only whether such an x exists.

If an unstructured search has M marked solutions among N candidates, classical random search requires, on average, approximately N/M queries when candidates are sampled uniformly. Grover’s algorithm requires O(√(N/M)) oracle queries, provided a coherent oracle can evaluate f and the problem is unstructured.

This is a query-complexity result. It does not automatically imply a practical speedup because state preparation, oracle construction, error correction, and measurement must also be included.

2.2 Optimization

An optimization problem seeks the best feasible assignment. In general form:

Here x is the decision vector, C(x) is the objective function, g_i and h_j are constraints, and X is the permitted domain. A feasible solution satisfies all constraints; an optimal solution has the best objective value among feasible solutions.

Quantum optimization methods often encode a discrete objective into a Hamiltonian. For binary variables x_i ∈ {0,1}, a quadratic unconstrained binary optimization (QUBO) model has the form:

The coefficients a_i and b_ij represent individual costs and pairwise interactions. Constraints can be incorporated using penalty terms. If a constraint is r(x) = 0, an unconstrained objective may be constructed as:

where λ > 0 is sufficiently large to discourage violations. The penalty must be chosen carefully: if too small, invalid solutions may be preferred; if excessively large, numerical scaling and hardware precision may suffer.

QUBO models can be mapped to Ising models using x_i = (1 − z_i)/2, where z_i ∈ {−1,+1}. The resulting energy function is measured by a quantum device or minimized by a hybrid method. Variational quantum optimization is heuristic in general; unlike Grover’s algorithm, it does not provide a universal quadratic speedup for arbitrary optimization problems.

2.3 Simulation

Simulation problems predict the behaviour of a physical or mathematical system. A quantum system with Hamiltonian H evolves according to the Schrödinger equation:

where |ψ(t)⟩ is the state, H is the Hamiltonian, ℏ is the reduced Planck constant, and t is time. Formally, for time-independent H:

Quantum simulation algorithms approximate the evolution operator or estimate properties such as ground-state energy. They are especially natural for quantum chemistry and materials because the target system itself is quantum mechanical. Accuracy depends on the Hamiltonian representation, basis choice, discretization, circuit approximation, and hardware noise.

2.4 Sampling

Sampling generates observations from a probability distribution. A quantum circuit prepares a state and measurement produces bit strings with probabilities determined by the state amplitudes. Sampling may support risk analysis, generative modelling, statistical physics, or verification of a quantum system.

If a circuit produces outcome x with probability p(x), repeated measurements estimate p(x). For an event A, the empirical frequency converges to its probability as the number of shots increases. Sampling does not necessarily mean that the full distribution can be reconstructed efficiently; the number of possible outcomes may grow exponentially with the number of qubits.

2.5 Estimation

Estimation asks for a numerical quantity rather than a particular configuration. Suppose a quantum procedure produces a success probability a. Amplitude estimation estimates a using a coherent quantum procedure. The classical sampling error of estimating a from S independent measurements is typically O(1/√S), whereas ideal amplitude estimation can achieve error O(1/T) using T coherent oracle applications, under its assumptions.

Amplitude estimation is useful for expected-value estimation, Monte Carlo risk calculations, option pricing, and integration. However, the quadratic improvement is meaningful only if state preparation and the required oracle can be implemented efficiently and coherently.

2.6 Integer factoring and discrete logarithms

Shor’s algorithm addresses structured number-theoretic problems. For factoring an integer N, it reduces factoring to period finding. Choose a suitable integer a relatively prime to N and consider:

The period r is the smallest positive integer satisfying aʳ ≡ 1 mod N. Quantum phase estimation and the quantum Fourier transform help determine information about r. Classical post-processing can then produce nontrivial factors with suitable probability, subject to conditions on a and r.

Shor’s algorithm is not a general search algorithm. Its relevance arises from algebraic periodicity. Large-scale fault-tolerant implementation would require error correction and substantially more resources than current noisy devices generally provide.

3. Major Algorithms and Their Mappings

Grover’s algorithm: unstructured search

Grover’s algorithm begins with a uniform superposition over candidate states, applies a phase oracle that marks valid candidates, and uses amplitude amplification to increase their probability. If there are N candidates and M marked states, the number of iterations is approximately:

for M much smaller than N and an appropriately known M. The exact optimum depends on the initial marked-state amplitude. If M is unknown, variants use adaptive or randomized iteration counts.

A suitable application must provide a reversible oracle. For example, a scheduling candidate can be encoded as a bit string, and the oracle can compute whether it satisfies all constraints. Converting a complex business rule into a low-depth reversible circuit may be more difficult than the search itself.

Shor’s algorithm: period finding

Shor’s algorithm is appropriate when a problem reduces to finding a hidden period or related algebraic structure. The quantum Fourier transform is applied after modular exponentiation, and measurement yields information from which the period can be inferred using continued fractions. Its power comes from interference that concentrates probability near useful frequency values.

Phase estimation

Given a unitary operator U and an eigenstate |ψ⟩ satisfying:

phase estimation approximates the eigenphase φ ∈ [0,1). If t precision qubits are used, the phase grid has spacing 1/2ᵗ; the exact error depends on the measurement procedure and success-probability guarantee. The eigenstate assumption is important. If the input is a superposition of eigenstates, the algorithm samples an eigenphase according to the corresponding amplitudes.

Phase estimation is a component of Shor’s algorithm and quantum simulation. In chemistry, if U is related to time evolution under H, eigenphase information can reveal an energy eigenvalue. The initial state must have sufficient overlap with the desired eigenstate.

Amplitude estimation

Let a unitary A prepare:

where the last qubit indicates a “good” event and a is its probability. Amplitude estimation estimates a. In finance, a may represent the probability-weighted contribution of a payoff after encoding a random variable. The payoff must be normalized to a permitted amplitude range, and rescaling must be reversed correctly after estimation.

Variational and hybrid methods

Variational algorithms use a parameterized circuit U(θ), measure an objective, and update parameters with a classical optimizer. For a Hamiltonian H, the variational energy is:

The variational principle states that E(θ) is at least the ground-state energy when the state is normalized and H is Hermitian. This makes the method useful for approximate ground-state estimation. It does not guarantee that a classical optimizer will find the global minimum of E(θ), especially in the presence of noise, barren plateaus, or poor ansatz design.

4. Encoding Practical Problems

Data encoding

A classical value may be encoded in computational-basis states, amplitudes, phases, angles, or Hamiltonian coefficients. Each choice has different preparation costs. Amplitude encoding can represent 2ⁿ values using n qubits in principle, but preparing the required amplitudes may be expensive. Therefore, a claimed exponential memory saving does not automatically imply an end-to-end advantage.

Constraints and oracles

Constraints can be handled by rejecting invalid states, adding penalty terms, using constraint-preserving operators, or designing a reduced representation containing only feasible states. Rejection is simple conceptually but can waste probability mass. Penalties are flexible but require scale selection. Constraint-preserving encodings may be efficient for special structures but difficult for irregular business rules.

Output and verification

Quantum measurements provide samples or estimates, not a classical description of the entire state. A successful mapping specifies:

• the required precision;
• the number of circuit repetitions;
• confidence or success probability;
• a classical verification procedure;
• acceptable approximation error;
• the cost of post-processing.

For optimization, the measured candidate should be checked against the original constraints and objective. For simulation, observables should be compared with analytical, experimental, or high-accuracy classical benchmarks where available.

5. A Decision Framework

The framework is a starting point, not a guarantee. A classical baseline must always be established. The relevant comparison may be exact enumeration, dynamic programming, Monte Carlo, mixed-integer programming, tensor-network simulation, or a specialized heuristic—not merely an arbitrary classical algorithm.

6. Worked Example: Facility Assignment as a QUBO

Consider two customers and two facilities. Let x_ij = 1 when customer i is assigned to facility j. The assignment constraint is:

Suppose assignment costs are c₁₁ = 3, c₁₂ = 5, c₂₁ = 4, and c₂₂ = 2. The original cost is:

Using penalty weight λ = 10, define:

For the feasible assignment x₁₁ = 1, x₁₂ = 0, x₂₁ = 0, x₂₂ = 1, the cost is 3 + 2 = 5 and both penalties are zero. For the alternative feasible assignment x₁₁ = 0, x₁₂ = 1, x₂₁ = 1, x₂₂ = 0, the cost is 5 + 4 = 9. Thus the first assignment is optimal among feasible assignments.

The penalty weight is not chosen because 10 is universally correct; it is illustrative. In a larger model, λ must be large enough to make violations unattractive relative to all feasible improvements, while remaining compatible with coefficient precision and hardware limitations. A hybrid quantum optimizer could search for low-energy bit strings, but the result must still be checked against the original assignment constraints.

7. Applied Case: Illustrative Portfolio-Risk Estimation

Background

An investment analytics team estimates the expected loss of a portfolio under uncertain market scenarios. Classical Monte Carlo simulation is accurate but requires many samples when the desired error is small.

Problem

Let L be a normalized loss variable and let μ = E[L] be the expected loss. The team wants an estimate within additive error ε with a specified confidence level.

Analysis

A quantum approach would need a unitary that prepares a distribution of market scenarios and encodes the normalized loss into an amplitude. Amplitude estimation can then estimate the corresponding success probability or expectation. In ideal query complexity, the dependence on precision can improve from O(1/ε²) for ordinary sampling to O(1/ε) for amplitude estimation.

Approach and solution

The workflow is:

1. Select a finite scenario model and define its probabilities.
2. Construct a reversible state-preparation circuit.
3. Encode loss values with sufficient numerical precision.
4. Build a payoff or threshold oracle.
5. Apply amplitude estimation.
6. Rescale the result to monetary units.
7. Validate against a classical Monte Carlo calculation.

Outcome

The quantum formulation is promising only if coherent state preparation and payoff evaluation are affordable. If loading market data dominates the circuit, the theoretical estimation advantage may disappear. The team should therefore report total runtime, circuit depth, repetitions, error bounds, and data-loading assumptions—not just the asymptotic amplitude-estimation result.

Learning points

The case demonstrates that algorithm choice follows the output type: expected loss is an estimation problem, not merely a search problem. It also demonstrates the importance of normalization, oracle construction, classical validation, and end-to-end resource accounting.

8. Challenges, Governance, and Professional Practice

Important limitations include finite coherence, gate errors, measurement noise, limited connectivity, costly error correction, imperfect initial states, and classical optimization overhead. Results may be biased by noise and by the choice of ansatz or penalty coefficients.

Data governance is also relevant. Financial, medical, or industrial data may be confidential or regulated. Quantum processing does not remove obligations concerning privacy, consent, auditability, fairness, or sector-specific compliance. A quantum model should document data provenance, encoding decisions, parameter choices, validation tests, and uncertainty.

Best practice includes:

• formulate the classical problem before selecting a quantum algorithm;
• establish a credible classical baseline;
• separate asymptotic complexity from practical resource estimates;
• make oracle and data-loading costs explicit;
• test small instances exhaustively;
• verify feasibility and objective values after measurement;
• report approximation error and confidence information;
• use hybrid methods when they are more realistic;
• avoid claiming quantum advantage without an end-to-end comparison.

Contemporary work increasingly combines quantum circuits with classical optimization, error mitigation, tensor-network methods, and domain-specific simulation. The important professional trend is not quantum-only computation but carefully designed quantum–classical workflows.

Chapter Summary

Problem mapping translates a practical question into a formal computational structure. Search problems may be addressed by Grover’s algorithm when an efficient oracle exists. Structured period-finding problems motivate Shor’s algorithm. Phase estimation estimates eigenphases and supports factoring and quantum simulation. Amplitude estimation targets probabilities and expectations, potentially improving the precision dependence of Monte Carlo methods. Optimization problems can be represented using QUBO or Ising models, although variational and hybrid methods are generally heuristic.

Effective mapping requires explicit variables, constraints, objectives, encodings, oracles, measurement procedures, error tolerances, and validation methods. Theoretical speedup alone is insufficient: state preparation, circuit construction, noise, post-processing, and classical alternatives determine practical value. Responsible quantum computing therefore combines algorithmic knowledge with modelling discipline, benchmarking, governance, and honest resource analysis.

Key Terms

Problem mapping: Translating a practical task into a mathematical and algorithmic form.

Oracle: A reversible quantum operation that evaluates or marks a condition.

Search problem: Finding an input that satisfies a specified predicate.

Grover’s algorithm: A quantum amplitude-amplification algorithm for unstructured search.

Amplitude amplification: Increasing the probability of marked states through interference.

Optimization: Selecting the best feasible solution according to an objective.

QUBO: Quadratic unconstrained binary optimization formulation.

Ising model: Optimization model using binary spin variables valued −1 or +1.

Penalty term: An added objective component that discourages constraint violations.

Simulation: Computing the behaviour of a physical or mathematical system.

Hamiltonian: Operator representing the energy or dynamics of a quantum system.

Sampling: Generating observations from a probability distribution.

Estimation: Computing an approximate numerical quantity from observations or amplitudes.

Amplitude estimation: Quantum method for estimating a success probability or expectation.

Phase estimation: Algorithm for estimating the phase of a unitary eigenvalue.

Shor’s algorithm: Quantum algorithm for factoring and related period-finding problems.

State preparation: Creating a quantum state representing input data or an initial condition.

Query complexity: Resource count based on calls to an oracle or black-box operation.

Hybrid algorithm: Method combining quantum circuits with classical computation.

Quantum advantage: Demonstrable improvement over relevant classical alternatives under stated conditions.

Review Questions

5 Short Answer Questions

1. What are the five basic components of a computational problem formulation?
2. State the query-complexity improvement promised by Grover’s algorithm for unstructured search.
3. Why are penalty terms used in QUBO models?
4. What kind of structure does Shor’s algorithm exploit?
5. Why must quantum measurement results be classically validated?

5 Long Answer Questions

1. Explain how a business problem can be mapped from plain language to a quantum algorithm, including encoding and verification.
2. Compare Grover’s algorithm, phase estimation, and amplitude estimation in terms of inputs, outputs, and applications.
3. Explain the construction of a QUBO model and discuss the effect of choosing an inappropriate penalty weight.
4. Describe the assumptions and practical limitations of quantum simulation for chemistry or materials science.
5. Discuss why theoretical quantum speedup may fail to produce practical end-to-end advantage.

3 Analytical / Application Questions

1. A logistics firm must select routes satisfying capacity constraints while minimizing cost. Formulate the decision variables, constraints, objective, and a possible QUBO mapping. Identify two risks in the mapping.
2. A risk analyst needs an expected loss estimate with progressively smaller error tolerance. Decide whether ordinary Monte Carlo or amplitude estimation is the more relevant formulation, and state the conditions that must be checked before claiming an advantage.
3. A scientist needs the lowest energy of a molecular Hamiltonian but cannot reliably prepare an exact ground state. Compare a variational method with phase estimation and recommend an approach for a noisy near-term device.

Multiple Choice Questions with Answers

Question 1

Which problem is most directly suited to Grover’s algorithm?

A. Finding a marked item in an unstructured database

B. Estimating the ground-state energy of a molecule

C. Factoring a large integer by period finding

D. Solving a linear system with a sparse matrix

Correct Answer: A. Finding a marked item in an unstructured database

Question 2

In a QUBO model, what is the main purpose of a penalty term?

A. To increase the number of qubits automatically

B. To discourage solutions that violate constraints

C. To remove all measurement noise

D. To prepare a uniform quantum state

Correct Answer: B. To discourage solutions that violate constraints

Question 3

What mathematical structure does Shor’s algorithm primarily exploit?

A. Random sampling

B. Unstructured enumeration

C. Algebraic periodicity

D. Gradient descent

Correct Answer: C. Algebraic periodicity

Question 4

If an unstructured search has N candidates and one marked candidate, Grover’s algorithm requires approximately how many oracle queries?

A. O(N²)

B. O(N)

C. O(log N)

D. O(√N)

Correct Answer: D. O(√N)

Question 5

In phase estimation, if U|ψ⟩ = e^(2πiφ)|ψ⟩, what quantity is estimated?

A. The eigenphase φ

B. The number of qubits only

C. The penalty coefficient

D. The measurement temperature

Correct Answer: A. The eigenphase φ

Question 6

Which task is most naturally formulated as an amplitude-estimation problem?

A. Finding whether any schedule is feasible

B. Estimating an expected financial loss

C. Factoring an integer

D. Encoding a binary variable

Correct Answer: B. Estimating an expected financial loss

Question 7

For the facility example, what is the cost of assigning customer 1 to facility 1 and customer 2 to facility 2?

A. 3

B. 4

C. 5

D. 9

Correct Answer: C. 5

Question 8

Which statement about a quantum oracle is correct?

A. It must be a reversible operation in a quantum circuit

B. It is always a classical database

C. It eliminates the need for measurement

D. It guarantees a practical speedup

Correct Answer: A. It must be a reversible operation in a quantum circuit

Question 9

What does the variational principle imply for a normalized trial state and a Hermitian Hamiltonian?

A. Its energy is always exactly the first excited-state energy

B. Its energy is no lower than the ground-state energy

C. Its energy is always zero

D. Its state preparation requires phase estimation

Correct Answer: B. Its energy is no lower than the ground-state energy

Question 10

Why is data loading important when evaluating a proposed quantum advantage?

A. Loading data can dominate the total computational cost

B. Data loading determines whether qubits obey superposition

C. Loading data removes the need for an oracle

D. Data loading guarantees fault tolerance

Correct Answer: A. Loading data can dominate the total computational cost