Feasibility, Benchmarking and Resource Estimation

Introduction

Quantum algorithms are often presented in terms of asymptotic speedups, but an algorithmic speedup does not automatically produce a useful engineering or economic advantage. A practical assessment must ask whether the required qubits can be built, whether the circuit can be executed before noise destroys its information, whether the processor has suitable connectivity, how many samples are needed, and whether a classical method remains cheaper or more reliable.

This chapter develops a practical framework for evaluating quantum-computing proposals. The focus is not merely on whether a quantum circuit is theoretically correct, but on whether it is feasible under realistic hardware, software, statistical and operational constraints. The same framework can be used to compare quantum annealing, gate-based quantum computing, hybrid quantum–classical workflows and classical baselines.

A useful feasibility study has four dimensions:

1. Technical feasibility: qubits, gates, depth, connectivity, memory and error rates.
2. Statistical feasibility: shots, confidence intervals, variance and error mitigation.
3. Operational feasibility: queue time, execution time, calibration, compilation and reproducibility.
4. Economic feasibility: hardware cost, cloud cost, engineering effort, energy and opportunity cost.

A quantum solution should therefore be evaluated as an end-to-end system rather than as an isolated circuit.

Learning objectives

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

• estimate logical and physical qubit requirements;
• distinguish circuit width, gate count and circuit depth;
• analyse hardware connectivity and routing overhead;
• estimate execution time and sampling cost;
• explain how noise and error mitigation affect resource requirements;
• design fair benchmarks against classical baselines;
• compare alternatives using technical, economic and operational metrics; and
• identify conditions under which a quantum approach is not yet justified.

1. From algorithmic possibility to practical feasibility

A quantum algorithm is algorithmically feasible if it can be expressed as a valid finite sequence of quantum operations. It is technologically feasible if available hardware can execute that sequence with acceptable fidelity. It is decision-useful if its output improves a real decision, prediction or computation sufficiently to justify its total cost.

These levels must not be confused. For example, an algorithm may require only 50 logical qubits in theory but millions of physical qubits after fault-tolerance overhead. Conversely, a noisy near-term algorithm may fit on a 100-qubit device but produce an estimate too imprecise to be useful.

A feasibility assessment normally begins with a resource profile:

2. Qubit requirements and circuit width

2.1 Logical qubits

A logical qubit is an abstract, error-corrected qubit. It is intended to preserve quantum information despite errors in its physical components. The number of logical qubits includes data qubits, ancilla qubits, work registers, output registers and temporary qubits needed by subroutines.

For a simple register, if an integer has maximum value N, the minimum number of qubits needed to represent it in binary is

where n is the number of qubits and N is the largest representable non-negative integer. This formula assumes ordinary binary encoding and does not include ancillas or error-correction overhead.

For a search space of size M, an index register requires

qubits. If M = 1,000, then n = ⌈log₂ 1,000⌉ = 10, because 2⁹ = 512 and 2¹⁰ = 1,024.

Encoding choice can dominate width. A one-hot encoding of M alternatives may require M qubits, while a binary encoding requires approximately log₂M qubits. However, one-hot encoding can simplify some operators and constraints. Resource estimation must therefore include both qubit count and circuit complexity.

2.2 Ancillas and temporary storage

Algorithms often require ancilla qubits for reversible arithmetic, oracle construction, phase estimation, uncomputation and error correction. A first-order estimate is

where each term counts simultaneously live logical qubits. This is not a gate-count formula; it is a width estimate. Qubits that are reused at different times need not all be counted simultaneously, but qubits that overlap in lifetime must be included.

A good resource report states whether its qubit count is:

• peak live qubits or total qubit uses;
• logical or physical qubits;
• algorithm-only or full application width; and
• inclusive or exclusive of measurement, reset and control hardware.

2.3 Physical qubits

Physical qubits are the hardware elements from which logical qubits are constructed. If one logical qubit requires an average of R physical qubits, then a rough estimate is

This estimate assumes that R includes the chosen code, code distance, syndrome-measurement ancillas, routing overhead and an allocation for faulty or unused devices. In practice, R is not a universal constant. It depends on physical error rates, gate set, decoder performance, target logical error rate, architecture and algorithm duration.

A more useful engineering statement is therefore a range, such as “approximately 1,000–10,000 physical qubits per logical qubit under the specified error-correction assumptions,” rather than a single unsupported number.

3. Circuit depth, gate count and critical path

Gate count is the total number of operations. Circuit depth is the number of sequential layers when operations that act on disjoint qubits are executed in parallel. Depth is often more important than gate count for decoherence because qubits must remain coherent during the critical path.

If a circuit has layer durations Δt₁, Δt₂, …, Δt_d, its idealized execution duration is

where d is circuit depth and Δtᵢ is the duration of layer i. If every layer has approximately equal duration Δt, then t_circuit ≈ dΔt. This approximation is valid only when measurement, reset, control latency and variable gate durations are negligible or separately added.

A circuit can have a large gate count but modest depth if operations are highly parallel. Conversely, a circuit with few gates may have large depth if they form a long dependency chain.

Important depth measures include:

• logical depth: depth before hardware mapping;
• compiled depth: depth after decomposition into native gates;
• scheduled depth: depth after timing constraints and resource conflicts; and
• fault-tolerant depth: depth including error-correction cycles.

The compiled and scheduled values are more relevant to hardware feasibility than the logical value.

4. Connectivity and routing overhead

Quantum processors do not generally allow every qubit to interact directly with every other qubit. The hardware coupling graph can be represented as G = (V, E), where V is the set of physical qubits and E is the set of permitted two-qubit interactions.

If a circuit requests a two-qubit gate between logical qubits located at nonadjacent vertices, the compiler must insert routing operations, often SWAP gates. A SWAP can be decomposed into three controlled-NOT operations in many gate sets, although the exact cost is hardware-dependent.

Routing affects:

• two-qubit gate count;
• circuit depth;
• exposure to gate and measurement errors;
• calibration requirements; and
• the number of physical qubits needed for layouts and movement.

A useful comparison is the routing overhead ratio:

where G₂,logical is the original number of two-qubit gates and G₂,compiled is the number after routing. The ratio is dimensionless and should be reported only when G₂,logical > 0.

Connectivity can be improved by selecting an encoding that matches the device graph, placing frequently interacting variables near each other, reducing long-range interactions and using hardware-native gates. A theoretically compact circuit may therefore be inferior to a slightly wider circuit that avoids extensive routing.

5. Noise, fidelity and error budgets

5.1 Sources of error

Quantum computations are affected by gate errors, decoherence, measurement errors, state-preparation errors, crosstalk, leakage and calibration drift. Errors may be stochastic, correlated, time-dependent or hardware-specific.

A simple independent-error model illustrates why depth matters. If each of N operations succeeds with probability 1 − p and errors are independent, the probability that all operations succeed is

where p is the average error probability per operation. This is a simplified model: real devices have different error rates for different gates and may exhibit correlated errors.

For small p, the approximation

is useful when Np is not large. For example, with N = 1,000 and p = 0.001, P_success ≈ 0.999¹⁰⁰⁰ ≈ 0.368. This does not mean that every computation simply fails; it indicates that an uncorrected circuit is substantially affected by accumulated errors.

5.2 Error budgets

An error budget allocates an acceptable total error among sources. If the permitted total error is ε_total, a conservative allocation may require

where the terms represent gate, measurement, state-preparation, control and modelling contributions. The additive form is an engineering approximation and is most defensible when contributions are small and not strongly correlated.

Error budgets should specify the relevant output metric. A small average gate error does not guarantee a small error in a particular expectation value, tail probability or optimization decision.

5.3 Error mitigation

Error mitigation attempts to reduce the effect of errors without fully correcting them. Methods include measurement-error mitigation, zero-noise extrapolation, probabilistic error cancellation, symmetry verification and virtual distillation.

Mitigation does not make a noisy computation free. It may increase the number of circuit executions, classical processing and estimator variance. If an estimator has standard deviation σ for one shot and S independent shots are used, the standard error of the sample mean is

This relationship assumes independent, identically distributed samples with finite variance. If mitigation increases effective variance by a factor F, the required sample count for the same precision can increase approximately by F².

6. Sampling cost and statistical precision

Many quantum algorithms estimate an expectation value by repeated measurement. If outcomes are bounded between −1 and 1 and the true expectation is μ, the sample mean from S shots has standard error approximately

where μ̂ is the estimate and σ is the standard deviation of a single measurement. For a binary measurement with success probability p, σ² = p(1 − p), so the worst-case variance is 1/4.

Using a normal approximation, an approximate two-sided confidence interval is

where α is the significance level and z_(1−α/2) is the corresponding standard-normal quantile. This approximation is less reliable for small samples or probabilities near zero and one; exact binomial or concentration bounds may then be preferable.

If the desired half-width is δ and the worst-case variance is 1/4, a conservative sample estimate is

For 95% confidence, z ≈ 1.96. If δ = 0.01, then S ≥ 1.96² ÷ (4 × 0.01²) ≈ 9,604 shots. This is only a statistical estimate and excludes additional shots needed for error mitigation, parameter optimization and repeated experiments.

The total shot count for an algorithm may be much larger than the shots for one circuit. Variational algorithms evaluate many parameter settings, observables and iterations. If K circuits are evaluated with S shots each, then

provided every circuit receives the same number of shots. Adaptive allocation may reduce cost by assigning more shots to influential or uncertain circuits.

7. Runtime estimation

End-to-end runtime should distinguish at least five components:

Here t_queue is waiting time, t_compile is compilation and scheduling time, t_transfer is data-transfer time, t_execute is quantum execution time and t_post is classical post-processing. For S shots and K distinct circuits,

where t_reset, t_measure and t_dead represent reset, measurement and system dead time. This expression assumes serial execution. Parallel execution, batching and simultaneous measurement can reduce wall-clock time, but may introduce resource contention.

Runtime should be reported in more than one form: quantum processing time, wall-clock time, queue-inclusive time and time to a statistically acceptable answer. A benchmark that reports only gate execution time may seriously understate operational cost.

8. Benchmarking against classical baselines

A quantum result has meaning only relative to a properly selected baseline. The baseline should solve the same problem, with the same input data, accuracy requirement, stopping rule and output definition.

8.1 Baseline categories

Useful baselines include:

• the best known exact classical algorithm for small instances;
• scalable heuristic or approximation algorithms;
• domain-specific industrial software;
• randomized algorithms with confidence intervals;
• tensor-network or matrix-product-state simulation where applicable; and
• a simple reference method used to verify correctness.

A classical baseline should be optimized fairly. Comparing an optimized quantum implementation with an unoptimized script is not evidence of quantum advantage.

8.2 Benchmark dimensions

The phrase quantum advantage should be used carefully. A narrow demonstration of lower circuit depth is not the same as application-level advantage. Stronger claims require a relevant problem, competitive accuracy, realistic overheads and a classical comparison at comparable scale.

8.3 Scaling analysis

Suppose a classical method has runtime T_C(n) and a quantum workflow has total runtime T_Q(n), including sampling and compilation. A crossover point n* would satisfy

However, equality of runtimes is not sufficient. The quantum method must also meet accuracy, reliability, availability and cost requirements. In practice, crossover estimates should be expressed as ranges because hardware performance and implementation overhead are uncertain.

9. Economic and operational metrics

Technical feasibility must be converted into decision metrics. A basic execution-cost estimate is

where C_access is quantum hardware or cloud access cost, C_engineering is development and maintenance cost, C_classical is classical pre- and post-processing cost, and C_validation is the cost of testing, benchmarking and governance.

Useful operational indicators include:

• cost per successful result;
• time to solution at a specified confidence level;
• number of human engineering hours;
• availability and queue reliability;
• repeatability across calibration cycles;
• portability across vendors; and
• sensitivity to hardware drift.

A quantum workflow with lower nominal execution cost may still be unattractive if it requires rare expertise, frequent recalibration or extensive classical optimization.

10. Worked example: estimating a noisy expectation-value experiment

Consider a circuit using 12 logical data qubits and 4 ancillas. The compiled circuit has depth 80, including 50 two-qubit-gate layers. Each circuit is measured with 10,000 shots. A variational procedure evaluates 30 parameter settings per iteration for 20 iterations.

The peak logical width is

The number of circuit evaluations is

The total shot count is therefore

Assume the scheduled duration of one shot, including circuit execution, reset, measurement and dead time, is 200 μs. The idealized execution time is

This excludes queueing, compilation, data transfer and post-processing. If mitigation doubles the number of required shots, the execution component becomes approximately 40 minutes. If the hardware executes four independent batches in parallel, the ideal wall-clock execution time may fall to approximately 10 minutes, but only if the required capacity and calibration conditions are available.

If a physical implementation uses an assumed average overhead of 100 physical qubits per logical qubit, the rough device requirement is

This is an illustrative planning estimate, not a hardware guarantee. The actual number depends on the error-correction code and target logical error rate. The example shows why width alone is insufficient: six million shots and 600 circuit instances dominate the operational assessment.

11. Applied case: illustrative molecular-property workflow

Background

A research group wants to estimate the ground-state energy of a small molecule using a variational quantum eigensolver (VQE). The group believes that a quantum processor may eventually help with larger active-space calculations.

Problem

The initial proposal reports a four-qubit ansatz and claims low resource requirements. However, it does not include orbital mapping, ancillas, Hamiltonian-term measurement, optimizer iterations or a classical reference calculation.

Analysis

The team first defines the target accuracy as 10 millihartree and selects a trusted classical diagonalization method for the same active space. It then maps the molecular Hamiltonian to qubits and counts the Pauli terms requiring measurement. The total workload is not one circuit but many circuits: different Pauli observables, parameter settings and optimization iterations.

The team measures logical width, compiled depth, two-qubit gates, shots per observable and optimizer evaluations. It also records the variance of each observable because high-variance terms require more samples. Measurement grouping is considered to reduce the number of distinct circuits, while symmetry verification is tested for its effect on bias and sampling cost.

Approach and solution

Three implementations are compared:

1. a classical exact reference for the selected active space;
2. an unmitigated quantum workflow; and
3. a mitigated quantum workflow with measurement-error correction and symmetry checks.

The comparison uses identical molecular geometry, basis set, energy tolerance and stopping criteria. The quantum result is accepted only if its confidence interval overlaps the target accuracy and its constraint checks pass.

Outcome

For the selected small molecule, the classical method is faster and more accurate. The quantum experiment nevertheless identifies which observables have high variance, quantifies the cost of mitigation and provides an experimentally useful noise profile. The group concludes that the near-term value is methodological rather than economic: the experiment supports hardware and algorithm development but does not yet replace the classical baseline.

Learning points

• A small qubit count does not imply a small total workload.
• Measurement terms and optimizer iterations can dominate runtime.
• Accuracy must be defined before comparing methods.
• A negative result is valuable when it identifies the conditions required for future advantage.

12. Best practices for resource estimation

1. Specify the problem instance and output metric. “Solve the problem” is not an adequate success criterion.
2. Separate logical and physical resources. State the error-correction and hardware assumptions.
3. Report pre- and post-compilation resources. Routing and gate decomposition can substantially change depth.
4. Include all repetitions. Count shots, observables, optimizer steps, amplitude-estimation rounds and validation runs.
5. Use ranges and sensitivity analysis. Vary error rates, shot counts, queue time and mitigation overhead.
6. Benchmark the complete workflow. Include classical preprocessing, quantum execution and post-processing.
7. Use matched baselines. Equalize accuracy, input, stopping rules and hardware conditions.
8. Track uncertainty. Report confidence intervals and uncertainty in runtime or cost estimates.
9. Record reproducibility information. Include software versions, compiler settings, device calibration data and random seeds where relevant.
10. Distinguish demonstration from deployment. A successful laboratory experiment may not satisfy production requirements.

13. Challenges, limitations and governance

Resource estimates are uncertain because quantum hardware changes rapidly and vendor-reported metrics may not predict application-level performance. Average error rates can conceal correlated errors, rare failures or drift. Cloud queue time may dominate execution but is often excluded from published demonstrations.

There are also governance concerns. Benchmark results should disclose whether data, classical preprocessing or post-selection were selected to favour the quantum method. Claims of advantage should be reproducible and should not rely on an artificially weak baseline. In regulated domains, such as finance, healthcare and energy, a quantum output must be auditable and comparable with approved classical procedures.

Security and confidentiality are additional concerns when proprietary data are submitted to external quantum cloud services. Organizations should define data classification, access control, retention and vendor-assurance requirements before experimentation.

14. Contemporary developments

Current work increasingly emphasizes application-oriented benchmarks, error-corrected resource estimates, logical-qubit performance, compiler-aware algorithm design and hybrid workflows. Benchmark suites are moving beyond raw qubit counts toward accuracy at fixed cost, time to solution and scaling with instance size.

Machine learning can assist compilation, calibration and parameter optimization, but it does not remove the need for statistical validation. AI-based optimizers may reduce iterations in some problems and increase them in others; their contribution must be measured experimentally against simpler optimizers.

Fault-tolerant resource estimation is also becoming more detailed. Estimates may include code distance, lattice-surgery operations, magic-state production, decoding throughput and physical control bandwidth. These estimates are essential for long-term algorithms such as large-scale factoring or precise simulation, but they remain conditional on hardware architecture and target logical error rates.

Chapter Summary

Feasibility assessment connects quantum algorithms with real hardware, statistical requirements and organizational decisions. The essential resources are logical and physical qubits, circuit depth, gate count, connectivity, sampling effort, runtime and error tolerance. Qubit width describes simultaneous storage, while depth describes sequential exposure to noise. Hardware connectivity can introduce routing overhead, particularly for two-qubit operations.

Noise must be analysed through an explicit error budget, and error mitigation should be evaluated together with its sampling and computational overhead. Expectation-value estimation generally improves only as 1 ÷ √S, so high precision can require many shots. End-to-end runtime includes queueing, compilation, data transfer, execution and post-processing.

A credible benchmark compares a complete quantum workflow with a strong classical baseline under matched accuracy and stopping conditions. Technical metrics should be combined with economic and operational measures such as cost per result, engineering effort, availability and reproducibility. At present, many quantum experiments are valuable as technology demonstrations even when a classical method remains superior for the immediate application. Professional judgment requires reporting that conclusion honestly and identifying the conditions under which the balance may change.

Key Terms

Ancilla qubit: A temporary qubit used for workspace, control, measurement or error correction.

Benchmark: A standardized experiment used to compare computational methods.

Circuit depth: The number of sequential operation layers in a circuit.

Connectivity: The pattern of physical-qubit pairs that can interact directly.

Error budget: An allocation of acceptable total error among different error sources.

Error mitigation: Techniques that reduce the observed effect of noise without full error correction.

Fault tolerance: The ability to perform reliable computation using error-corrected components.

Gate count: The total number of quantum operations in a circuit.

Logical qubit: An encoded qubit intended to be more reliable than an individual physical qubit.

Measurement variance: The variability of measurement outcomes around their expectation value.

Physical qubit: A hardware implementation of a quantum two-level system.

Routing overhead: Additional operations required to satisfy hardware connectivity.

Sampling cost: The number of circuit repetitions required to estimate an output with specified precision.

Standard error: The estimated standard deviation of a statistic, often decreasing as 1 ÷ √S.

Statistical confidence interval: A range constructed by a specified statistical procedure to express estimation uncertainty.

Time to solution: The time required to obtain an answer meeting predefined accuracy and reliability criteria.

Variational algorithm: A hybrid algorithm that optimizes classical parameters controlling a quantum circuit.

Width: The maximum number of simultaneously active qubits.

Review Questions

Short Answer Questions

1. Distinguish logical qubits from physical qubits.
2. Why can circuit depth be more important than total gate count?
3. What is routing overhead, and why does connectivity cause it?
4. State the relationship between sampling error and the number of shots.
5. Name four components of end-to-end quantum runtime.

Long Answer Questions

1. Explain how encoding choice, ancillas and error correction influence qubit-resource estimation.
2. Discuss why a quantum benchmark must include a strong and fairly configured classical baseline.
3. Explain the advantages and limitations of error mitigation for near-term quantum computing.
4. Describe a complete methodology for estimating the runtime of a variational quantum algorithm.
5. Discuss technical, economic and operational criteria for deciding whether a quantum workflow is deployment-ready.

Analytical / Application Questions

1. A circuit has 20 data qubits, 6 ancillas and an assumed physical-to-logical overhead of 80. Estimate its logical width and rough physical-qubit requirement. State why the estimate is conditional.
2. A measurement has standard deviation 0.5 and uses 2,500 independent shots. Estimate its standard error using SE = σ ÷ √S. Explain how many shots would be needed to halve the standard error.
3. A quantum method is faster in raw gate-execution time but requires ten times more samples and has a long cloud queue. Design a benchmark that determines whether it provides application-level advantage over a classical method.

Multiple Choice Questions with Answers

Question 1

A search space contains 1,000 alternatives. Using binary encoding, what is the minimum number of qubits required for an index register?

A. 8

B. 9

C. 10

D. 11

Correct Answer: C. 10

Question 2

Which resource measures the number of sequential operation layers in a quantum circuit?

A. Circuit width

B. Circuit depth

C. Shot count

D. Connectivity degree

Correct Answer: B. Circuit depth

Question 3

What is the main purpose of inserting SWAP operations during compilation?

A. To increase measurement precision

B. To correct all gate errors

C. To satisfy hardware connectivity constraints

D. To reduce the number of logical qubits

Correct Answer: C. To satisfy hardware connectivity constraints

Question 4

Under the independent-operation model, what is the probability that N operations all succeed when each operation has error probability p?

A. pᴺ

B. (1 − p)ᴺ

C. N(1 − p)

D. 1 − pᴺ

Correct Answer: B. (1 − p)ᴺ

Question 5

If a measurement has standard deviation σ and uses S independent shots, which expression gives its standard error?

A. σS

B. σ ÷ S

C. σ ÷ √S

D. √σ ÷ S

Correct Answer: C. σ ÷ √S

Question 6

Which item is normally part of end-to-end quantum runtime?

A. Only two-qubit gate duration

B. Queueing and post-processing

C. Only the number of logical qubits

D. Only classical benchmark runtime

Correct Answer: B. Queueing and post-processing

Question 7

A circuit is executed 600 times with 10,000 shots per execution. What is the total shot count?

A. 60,000

B. 600,000

C. 6,000,000

D. 60,000,000

Correct Answer: C. 6,000,000

Question 8

Which statement best describes error mitigation?

A. It always eliminates the need for repeated measurements.

B. It reduces noise effects but can increase variance and sampling cost.

C. It converts every physical qubit into a logical qubit.

D. It guarantees fault-tolerant computation.

Correct Answer: B. It reduces noise effects but can increase variance and sampling cost.

Question 9

For a fair quantum–classical benchmark, which condition is most important?

A. Use the weakest available classical implementation.

B. Compare different input instances to avoid duplication.

C. Use matched accuracy, input data and stopping criteria.

D. Exclude classical preprocessing from both methods.

Correct Answer: C. Use matched accuracy, input data and stopping criteria.

Question 10

If the standard error must be reduced by a factor of two, approximately how must the number of independent shots change?

A. It must be halved.

B. It must remain unchanged.

C. It must be doubled.

D. It must be quadrupled.

Correct Answer: D. It must be quadrupled.