The Bitter Truth About Quantum Algorithms in the NISQ Era

Frank Leymann; Johanna Barzen

Source-linked AI summary

The Bitter Truth About Quantum Algorithms in the NISQ Era

Frank Leymann, Johanna Barzen

arXiv:2006.02856v2Jun 4, 2020quant-ph

TL;DR

The paper addresses the gap between describing a quantum algorithm and determining whether its implementation can execute successfully on a noisy, resource-limited NISQ device. It analyzes how state preparation, oracle expansion, hardware connectivity, circuit rewriting, and readout affect implementation requirements, concluding that these factors must be assessed together. It also reports that full error correction and even protecting individual qubits are impractical on current NISQ machines because of resource overhead.

Problem
NISQ execution assessment cannot rely on the algorithm’s unitary transformation alone; state preparation, measurement, subroutines, and hardware effects also determine circuit requirements.
Method
The paper discusses the main implementation factors that increase depth, width, or noise, including state preparation, oracle expansion, connectivity, circuit rewriting, and readout.
Results
Full error correction is unavailable on current NISQ machines, while protecting individual qubits increases overhead and makes even simple algorithms impractical.
Takeaways & Limitations
Developers should inspect the complete hardware-specific circuit, rather than only the algorithm proper, when assessing executability on a NISQ device.
Takeaways & Limitations
Oracle expansion can become much more complex than illustrative circuits because expansion is recursive and may require operations such as multiplication.

Abstract

from arXiv · show

Implementing a quantum algorithm on a NISQ device has several challenges that arise from the fact that such devices are noisy and have limited quantum resources. Thus, various factors contributing to the depth and width as well as to the noise of an implementation of an algorithm must be understood in order to assess whether an implementation will execute successfully on a given NISQ device. In this contribution, we discuss these factors and their impact on algorithm implementations. Especially, we will cover state preparation, oracle expansion, connectivity, circuit rewriting, and readout: these factors are very often ignored when presenting an algorithm but they are crucial when implementing such an algorithm on near-term quantum computers. Our contribution will help developers in charge of realizing algorithms on such machines in (i) achieving an executable implementation, and (ii) assessing the success of their implementation on a given machine.

1. Introduction

Assessing a quantum algorithm for NISQ execution requires analyzing more than its central unitary transformation. Hardware noise, limited qubits, preprocessing, hybrid iteration, compilation, and circuit complexity all affect executability.

1. Introduction: NISQ devices’ noise and limited qubit counts make algorithm depth and width key indicators of execution success.Qubit states and gates are erroneous, while current hardware has limited scalability.
1.1. The Impact of Hardware on Quantum Algorithms: For 50 qubits and an error rate of about 10^-3, the depth must be significantly less than 20 to avoid excessive imprecision.The paper presents this as a rule-of-thumb example for assessing execution limits.
1.1. The Impact of Hardware on Quantum Algorithms: Quantum advantage requires shallow algorithms using many qubits, because deep algorithms using few qubits can remain classically simulable.The paper connects shallow depth to NISQ capabilities and classical simulation limits.
1.2. The Consequence: Successful execution assessment must include state preparation, measurement, oracle subroutines, target-machine effects, and the resulting circuit’s depth and width.The unitary transformation alone does not determine the requirements of the circuit finally executed on hardware.
1.3. Contributions: The paper raises awareness of implementation complexity, discusses its main sources, and details the tasks needed to produce executable NISQ circuits.These are presented as the paper’s three high-level contributions.

2. Input Preparation

Input preparation converts classical data into quantum states through classical preprocessing and hardware-specific state-preparation circuits. Encoding choices trade representational compactness against preparation complexity, so their additional gates and qubits must be included when assessing executability.

Input preparation: Input preparation combines preprocessing, which creates a circuit, with state preparation, which executes that circuit on a quantum computer.The circuit is prepended to the algorithm proper and represented in the target device’s instruction language.
Encoding choices: Encoding choice depends on the intended computation: digital encoding supports arithmetic manipulation, whereas analogue encoding exploits the device’s Hilbert space.The paper distinguishes basis, amplitude, and product encodings as examples of these approaches.
Basis encoding: Basis encoding approximates each real number with binary digits and a sign bit, requiring (n+k+2) bits per number.Vectors are encoded by concatenating the basis encodings of their components; data sets can be represented as uniform superpositions of encoded elements.
Product encoding: Product encoding represents each component with a single-qubit state and can be prepared using one rotation per qubit.This encoding requires n qubits for n-dimensional data and is directly useful for quantum neural-network processing.
Conclusion on input preparation: Input preparation overhead must be counted alongside the algorithm proper because it contributes additional gates and qubits required for execution.The paper treats this overhead as necessary for evaluating whether an algorithm is executable on a particular device.

3. Oracle Expansion

Oracle-based algorithms must expand black-box functions into quantum circuits, recursively when necessary, because these substitutions determine executable depth and width on NISQ devices.

Oracle query complexity counts invocations, but each oracle is itself a quantum algorithm that can significantly increase the enclosing circuit’s depth and width.
Expanding all oracles is critical for assessing NISQ suitability because it reveals time complexity as depth and space complexity as width.
Addition circuits use QFT and QFT−1 as further black boxes, so oracle expansion continues beyond the initially visible arithmetic operation.
Shor’s oracle performs modular exponentiation requiring multiplication and further circuits, making its recursive expansion substantially more complex than the summation example.
Oracle expansion replaces black-box functions with circuits and recursively expands any further black boxes contained within those circuits.
Black-box implementations often require ancilla qubits, so expansion can increase width as well as circuit depth.

4. Considering Connectivity

Limited and nonuniform hardware connectivity forces logical circuits to be rewritten with qubit movement and device-specific mappings, affecting depth, gate count, and success rates.

A topology graph represents physical qubits as nodes and direct hardware connections as edges; 2-qubit operations require the participating qubits to be adjacent.
Missing connectivity requires SWAP gates or qubit remapping, and the added operations increase depth and negatively affect total error rates.
In the sample rewrite, replacing parallel CNOT operations with sequential SWAP and CNOT operations increases circuit depth by 2.
Each SWAP is typically decomposed into three CNOT gates, further increasing the gate count of the hardware-specific circuit.
Weighted topology graphs encode connection success rates, so minimizing SWAP count alone may select a lower-success route.
Connection success rates change over time, requiring regular measurement and making the weighted topology graph time dependent.
Compiler output should be inspected because topology-induced depth increases are part of evaluating whether an algorithm can execute on a particular machine.

5. Circuit Rewriting

Circuit rewriting adapts hardware-independent algorithms to a target device by changing gates, scheduling, mappings, and connectivity-related operations, with device-dependent effects on depth and noise.

A transpiler maps algorithm gates to physically supported gates while optimizing width, depth, excited-state time, and target-device connectivity.
Rewriting the sample circuit from four levels to two demonstrates depth reduction through gate rescheduling and deletion of empty levels.
Transpilation changes both gates and qubit allocation or movement, which can significantly alter the original circuit depth.
Transpilation increased depth from 3 to 9 in one experiment after substitutions and added SWAPs.
In another experiment, three sequential gates were replaced by one U2 gate, reducing depth from 3 to 1.
The same original circuit produced different transpiled results across devices: one preserved depth, while another increased it from 3 to 8.
Depth can be reduced by shifting gates leftward into parallel levels without changing the circuit’s specified data flow.

6. Correcting Readout Errors

Readout errors distort measured result distributions because measurement takes time and is affected by decoherence. The section presents matrix inversion as a calibration-based correction method for small NISQ devices, with recurring calibration and classical postprocessing overhead.

Sources of readout error: Measurement can introduce readout errors because measured qubits may change state during the relatively long measurement process.These errors make measured distributions differ from the true distributions.
Unfolding: Unfolding estimates the undisturbed result distribution from the disturbed distribution produced by repeated measurements.The measured bit-string frequencies form vector m, while the true distribution is represented by vector t.
Matrix inversion: Matrix inversion models the distributions as m = C·t and returns t = C−1·m when the calibration matrix C is invertible.The matrix coefficients represent conditional probabilities of measuring value i given prepared state k.
Calibration cost: 2^n measurements are required, making calibration practical only for small qubit counts; a 20-qubit calibration matrix entails about 10^6 entries.The method requires preparing and measuring every possible computational-basis state.
Operational overhead: The calibration matrix is device-dependent and drifts over time, so it must be determined regularly, although its inverse can be reused for multiple postprocessing steps.Calibration circuits produce the matrix rows, after which the inverse is applied to measured algorithm results.
Operational overhead: Matrix inversion imposes both recurring calibration overhead and classical postprocessing overhead for each algorithm execution.For sufficiently small readout errors, related experiments found several unfolding methods acceptable, though matrix inversion was not the best method.

7. Provenance

Provenance is presented as a uniform metadata basis for assessing whether devices can execute circuits successfully and for transforming circuits appropriately. The proposed information spans circuit properties, device characteristics, calibration data, and capability metrics.

Purpose: Provenance supports assessing device appropriateness and transforming quantum algorithms into circuits that deliver acceptable results on particular devices.This requires metadata about both algorithms and quantum hardware.
Required metadata: Circuit provenance includes hardware-independent gates, depth, and width, together with information from hardware-dependent transpilation.This information can be derived by inspecting circuits or obtained from a device transpiler.
Required metadata: Device provenance includes available qubits, connectivity, supported gates, decoherence times, and error rates for operations and connections.The section distinguishes static device properties from dynamic calibration-related values.
Capability assessment: Quantum-device capability can also be represented using metrics such as quantum volume and total quantum factor.These metrics are proposed for specifying or assessing processing power.
Architecture: A vendor-independent provenance database should combine static and dynamic information to support circuit assessment and transformation.The described architecture uses analyzers, collectors, and an aggregator for circuit, device, transpilation, and calibration information.

8. Outlook: Error Correction “in the Small”

The section examines whether limited error correction can improve NISQ computations without consuming infeasible resources. It concludes that full correction is unrealistic and that even protecting selected qubits was impractical in the reported experiments.

Scope of error correction: Full quantum error correction is unrealistic on NISQ machines because it requires additional qubits and quantum subroutines.The available quantum resources are too sparse for comprehensive correction in this setting.
Logical qubits: A logical qubit bundles multiple physical qubits so errors can be detected and corrected through encoding, syndrome computation, and recovery.The illustrated encoding maps α|0⟩+β|1⟩ to α|000⟩+β|111⟩ using two additional qubits.
Resource overhead: Protecting one physical qubit requires four additional qubits plus encoding, correction, and logical-gate subroutines.The original algorithm’s gates must be replaced by corresponding operations on logical qubits.
Resource overhead: Logical-qubit implementations substantially increase both circuit depth and width, making them too expensive for current NISQ machines.This overhead conflicts with the requirement that width times depth remain very small.
Individual-qubit protection: Experiments found protecting individual qubits on small machines too erroneous to be realistic, leaving the proposed restricted approach unvalidated.The experiments neither proved nor disproved the underlying hypothesis.
Conclusion: Even protecting individual important qubits increased errors in already simple algorithms, making error correction “in the small” impractical.This restricted approach did not avoid the practical limitations of NISQ devices.

9. Conclusion and Future Work

The conclusion argues that successful NISQ implementation requires analyzing the full execution pipeline rather than the algorithmic unitary alone. It highlights state preparation, oracle circuits, device topology, rewriting, readout correction, provenance, and the impracticality of small-scale error correction.

Conclusion: State preparation may require significant classical preprocessing and a preparation circuit that substantially increases the algorithm’s depth.The preparation circuit can add depth beyond the quantum algorithm proper.
Conclusion: Oracle subroutines must be specified as circuits and can contribute crucially to both the depth and width of the algorithm.Treating an oracle as an abstract subroutine does not capture its implementation cost.
Conclusion: The target device’s topology increasingly affects algorithm depth, and this impact is time-dependent.Connectivity therefore belongs among the hardware-specific factors considered during implementation.
Conclusion: Hardware-independent gate shifting and hardware-specific transpilation can both affect circuit depth and should be considered during optimization.The conclusion identifies reducing depth and width before or during transpilation as useful optimization opportunities.
Conclusion: Readout correction requires regularly determining a device calibration matrix and applying it to every result through classical postprocessing.The matrix inversion method leaves the quantum algorithm proper unchanged but adds calibration and postprocessing work.
Conclusion: Provenance metadata is needed to derive and assess the implementation information required by these tasks.The paper sketches how such metadata can be collected and used.
Future work: Experiments found even individual-qubit error correction impractical, while future work targets patterns and a NISQ Analyzer for assessing execution success.The proposed analyzer is intended to evaluate whether an algorithm may execute successfully on a particular quantum computer.

Appendix A: Impact of Error Rates on IBM Quantum Experience

The experiment examines how topology and initial qubit allocation affect circuit rewriting on IBM Quantum Experience devices. A simple circuit applies X, CNOT, and measurement operations.

The experiment tests topology-dependent rewriting and initial qubit allocation on three IBM Quantum Experience devices.It applies a CNOT between qubits that are nonadjacent in the topology graph.
The circuit negates q[1], applies CNOT(q[1], q[4]), and measures q[4] in the computational basis.The measurement is irrelevant to the subsequent analysis.
Figure 26 depicts the circuit used to assess topology effects on circuit rewriting.

A.1 ibmq_oursense

Transpilation selects physical qubits and inserts SWAPs according to operation and connection success rates. Recalibration and device topology can therefore change the resulting circuit and allocation.

ibmq_oursense: For ibmq_ourense, q[1] maps to physical qubit 3 and q[4] to physical qubit 0 before rewriting.Physical qubit 3 provides a suitable success rate for the X operation.
ibmq_oursense: Transpilation minimizes errors by prioritizing CNOT success rates over single-qubit gate success rates when allocating qubits.This can select positions with higher single-qubit error rates if required CNOT errors are lower.
ibmq_oursense: A SWAP moves q[1] from physical qubit 3 to qubit 1 so CNOT(1,0) realizes CNOT(q[1],q[4]) on a high-success-rate connection.The SWAP is represented as three CNOTs in the rewritten circuit.
ibmq_london: On ibmq_london, q[1] maps to qubit 3 and q[4] to qubit 0, then q[4] is swapped to qubit 1 for CNOT(3,1).
ibmq_london after recalibration: After recalibration, ibmq_london retains the initial allocation but targets connection (0,1), swapping q[1] to qubit 1 for CNOT(1,0).The topology weights and colors changed after recalibration.
ibmq_16_melbourne: On ibmq_16_melbourne, q[1] maps to qubit 13 and q[4] to qubit 2, then q[1] is swapped to qubit 12 for CNOT(12,2).The selected connection has a very high success rate.

Appendix B: Measuring the Calibration Matrix

The calibration-matrix experiment measures selected rows on ibmq_rome by executing a circuit repeatedly and examining the resulting histograms.

Selective rows of ibmq_rome’s calibration matrix are measured using circuit Cs executed with 1024 shots.
The resulting histogram reports percentages for outcomes exceeding a threshold, with outcomes below it treated as unmeasured.Measured values are shown on the histogram’s x-axis.
Figures 31–33 show measurements of the C0, C1, and C31 rows of ibmq_rome’s calibration matrix.

Appendix C: Error Correction “in the Small”

The error-correction experiments compare ideal, simulated-noise, and hardware execution. Although simulation recovered the introduced bit flip perfectly, hardware accuracy was low and the authors question protecting individual qubits this way.

The error-correction circuit has depth 14 and prepares, encodes, syndromically analyzes, and recovers the state of q[0].
With an inserted q[1] bit flip, simulation produced the correct result 00111 with 100% probability.The error was correctly detected and recovered.
Hardware execution of the transpiled circuit on ibmq_16_melbourne produced the correct result 00111 with probability 10.229%.The run used 8192 shots, and several erroneous results were more probable.
With noise introduced, hardware execution produced 00111 with probability 7.312%.Several erroneous results again occurred with higher probability.
The experiments do not suggest protecting individual qubits with error correction on NISQ machines.The authors identify the significant depth increase from injecting the correction circuit as one possible reason.