Simon's Algorithm in the NISQ Cloud

Basic Information

• Paper ID: 2406.11771
• Title: Simon's algorithm in the NISQ cloud
• Authors: Reece Robertson, Emery Doucet, Ernest Spicer, Sebastian Deffner
• Classification: quant-ph cs.ET
• Publication Date: June 18, 2024 (arXiv preprint)
• Paper Link: https://arxiv.org/abs/2406.11771

Abstract

Simon's algorithm is one of the earliest problems demonstrating genuine quantum advantage. However, the algorithm assumes access to noiseless qubits. This study uses Simon's algorithm to benchmark the error rates of devices currently available in the "quantum cloud." The primary results provide an objective comparison of different physical platforms offered by IBM and IonQ. The research emphasizes the importance of understanding device architecture and chip topology when transpiling quantum algorithms to hardware. For instance, it demonstrates that dual-qubit operations between spatially separated qubits on superconducting chips should be avoided.

Research Background and Motivation

Problem Context

1. Gap between theoretical and practical quantum advantage: Simon's algorithm theoretically offers exponential quantum speedup, but this is based on the assumption of noiseless qubits, whereas current NISQ (Noisy Intermediate-Scale Quantum) devices exhibit significant noise.
2. Need for NISQ device performance evaluation: With surging quantum computing investments (projected market size of 1.3 trillion dollars by the mid-2030s), objective evaluation of current quantum cloud device performance is essential.
3. Challenges in algorithm porting: Different quantum hardware platforms (superconducting vs. ion trap) have distinct architectural characteristics, requiring understanding of how these differences impact algorithm performance.

Research Motivation

• Simon's algorithm is highly sensitive to noise, making it an ideal tool for NISQ device noise diagnostics
• Lack of systematic comparative studies across different quantum cloud platforms
• Need to understand the specific impact of hardware topology on algorithm performance

Core Contributions

1. Systematic benchmarking: First comprehensive error rate benchmarking of multiple IBM and IonQ quantum devices using Simon's algorithm
2. Platform comparative analysis: Provides objective performance comparison between superconducting qubits (IBM) and ion trap (IonQ) platforms
3. Topology dependency discovery: Demonstrates the significant negative impact of qubit spatial separation on superconducting platform performance
4. Noise model validation: Reveals that existing noise simulators cannot accurately predict real hardware behavior
5. Quantum advantage threshold analysis: Determines the specific gap between current NISQ devices and true quantum advantage

Methodology Details

Task Definition

Simon's Problem: Given a function f, determine whether it is a one-to-one function or a two-to-one periodic function with secret string s; if the latter, find s.

Mathematical formulation: For n-bit string inputs, f is either one-to-one, or for any two inputs x₁ and x₂ mapping to the same output, x₁ ⊕ x₂ = s.

Algorithm Implementation

Quantum Circuit Structure

1. Initialization: Two n-qubit registers, both initialized to |0⟩ state
2. First Hadamard transform: Apply H gates to the first register, creating uniform superposition
3. Oracle operation: Apply Uₓ, implementing Uₓ(|x⟩|y⟩) = |x⟩|f(x)⊕y⟩
4. Second Hadamard transform: Apply H gates to the first register again, producing interference patterns
5. Measurement: Measure all qubits, extracting results orthogonal to secret string s

Oracle Implementation Variants

Complex Oracle: Uses maximum number of two-qubit gates

• Contains multiple CNOT gates and single-qubit rotations
• Tests hardware performance under maximum entanglement operations

Simple Oracle: Uses minimum number of two-qubit gates

• Minimizes entanglement operations
• Serves as baseline for performance comparison

Performance Evaluation Metrics

Algorithm error rate: Defined as the percentage of iterations returning results not orthogonal to secret string s

• Should be 0% in ideal case
• 50% error rate equivalent to random guessing, indicating complete algorithm failure

Experimental Setup

Test Platforms

IBM Superconducting Platform

• Devices: Brisbane, Osaka, Kyoto (all 127-qubit Eagle chips)
• Characteristics: Fixed connectivity topology, requiring SWAP gates for long-distance operations
• Noise model: IBM AER local simulator, including single/two-qubit gate errors and readout errors

IonQ Ion Trap Platform

• Devices: Harmony (11 qubits), Aria (25 qubits), Forte (32 qubits)
• Characteristics: Fully connected topology, direct operations possible between any qubits
• Advantages: Higher precision, predictability, and coherence time

Experimental Parameters

• Problem scale: n ∈ 2, 12 (corresponding to 4-24 qubits)
• Repetitions: 3 experiments per configuration, 30 for simulators
• Qubit allocation: IBM systems allowed dynamic optimization of physical qubit selection
• Calibration updates: Latest noise characteristics obtained before each experiment

Experimental Results

Main Findings

1. Overall Performance Trends

• All NISQ devices show increasing error rates with problem size
• Critical threshold: Around 12 qubits, complex Oracle error rates approach 50%
• Quantum advantage prediction: Extrapolating to 53 qubits, all devices would reach 50% error rate

2. Platform Differences

IBM Superconducting Platform:

• Complex Oracle: Non-linear error growth, sharp deterioration for n>8
• Simple Oracle: Good performance, maintaining low error rates
• Spatial separation impact: CNOT gate error rates increase significantly with qubit distance

IonQ Ion Trap Platform:

• Error rates show consistent linear growth pattern
• Fully connected topology avoids spatial separation issues
• Overall performance more predictable

3. Simulator vs. Real Hardware

• IBM: Noise simulator severely underestimates complex Oracle error rates
• IonQ: Simulator predicts correct trends but underestimates errors by ~2x
• Key issue: Existing noise models insufficiently account for correlated errors

Quantitative Results

Physical Parameter Comparison

Spatial Separation Impact

On IBM platforms, CNOT gate error rates show clear growth trends with distance between control and target qubits, an effect the noise simulator fails to accurately capture.

Related Work

Quantum Algorithm Benchmarking

• Historical research: Early small-scale implementations of Shor's algorithm, random circuit sampling, Grover search, etc.
• NISQ evaluation: Previous studies show IBM, Rigetti, IonQ, and DWave devices have not achieved fair sampling

Hidden Subgroup Problem

• Theoretical framework: Simon's algorithm as representative of hidden subgroup problems, alongside Shor's algorithm, Deutsch-Jozsa algorithm, etc.
• Quantum advantage: Among first algorithms proving quantum Turing machines can violate Church-Turing thesis

NISQ Device Characteristics

• Noise modeling: Existing research primarily focuses on random Pauli noise; this work reveals real hardware complexity
• Device comparison: Lack of systematic comparative studies across different physical platforms

Conclusions and Discussion

Main Conclusions

1. NISQ limitations: Current quantum cloud devices remain too noisy to support true quantum advantage
2. Architecture importance: Understanding device architecture and chip topology is crucial for algorithm transpilation
3. Spatial effects: Dual-qubit operations between spatially separated qubits on superconducting chips should be avoided
4. Simulator insufficiency: Existing noise simulators cannot accurately predict real hardware behavior

Technical Insights

Superconducting Platform Optimization Strategies

• Algorithm design must consider qubit connectivity topology
• Minimize long-distance operations requiring SWAP gates
• Dynamic qubit allocation can partially mitigate topology limitations

Ion Trap Platform Advantages

• Full connectivity simplifies algorithm implementation
• Better error predictability
• Current qubit count limitations remain primary bottleneck

Limitations

1. Algorithm specificity: Conclusions primarily based on Simon's algorithm; other algorithms may perform differently
2. Time dependency: Quantum device performance continuously improves; conclusions have temporal limitations
3. Scale limitations: Constrained by device capabilities; unable to test larger-scale problems
4. Cost constraints: IonQ Forte testing limited by budget; fewer data points

Future Directions

1. Extended algorithm range: Test Deutsch-Jozsa, Bernstein-Vazirani, Shor's algorithms
2. Noise tolerance: Research noise tolerance thresholds for Simon's algorithm while maintaining quantum advantage
3. Boolean linear systems: Develop efficient algorithms for solving noisy Boolean linear equations
4. Hardware improvements: Track impact of device performance improvements on algorithm performance

In-Depth Evaluation

Strengths

1. Strong systematicity: First comprehensive Simon's algorithm benchmarking across multiple quantum cloud platforms
2. High practical value: Provides important reference for quantum algorithm developers selecting appropriate platforms
3. Important discoveries: Reveals significant impact of spatial separation on superconducting platform performance
4. Scientific methodology: Effectively isolates different factors through complex/simple Oracle comparison
5. Open data: Provides complete code and data supporting result reproducibility

Weaknesses

1. Algorithm limitations: Tests only Simon's algorithm; generalizability of conclusions needs verification
2. Scale limitations: Maximum tested scale (24 qubits) still far from quantum advantage threshold
3. Temporal relevance: Rapid NISQ device development may quickly render conclusions obsolete
4. Insufficient theoretical analysis: Lacks deep theoretical explanation of observed phenomena
5. Cost constraints: Some experiments limited by budget; data completeness could be improved

Impact

Academic Contributions:

• Provides new benchmarking methodology for NISQ device performance evaluation
• Reveals important impact of hardware topology on algorithm performance
• Provides data supporting time expectations for quantum advantage realization

Practical Value:

• Guides quantum algorithm developers in selecting appropriate hardware platforms
• Provides directions for quantum cloud service providers to improve devices
• Offers reference for investors evaluating quantum computing development stage

Reproducibility:

• Provides complete GitHub code repository
• Detailed description of experimental setup and parameters
• Uses publicly accessible quantum cloud platforms

Applicable Scenarios

1. NISQ algorithm development: Provides hardware selection guidance for developers
2. Quantum cloud service evaluation: Helps users select appropriate quantum computing platforms
3. Hardware improvement guidance: Provides optimization directions for quantum device manufacturers
4. Educational research: Serves as practical case study for quantum computing courses
5. Investment decisions: Provides technical status reference for quantum computing investments

References

This paper cites 47 important references, primarily including:

• Simon, D.R. (1997): Original Simon's algorithm paper
• Nielsen & Chuang (2010): Classical quantum computation and quantum information textbook
• Preskill, J. (2018): Foundational NISQ era paper
• IBM and IonQ technical documentation and API specifications
• Related work on recent quantum advantage experiments

Summary: This paper conducts systematic benchmarking of mainstream quantum cloud platforms using Simon's algorithm, revealing performance limitations of NISQ devices and characteristics of different hardware architectures. Research results hold important practical value for the quantum computing field, but also demonstrate considerable distance remains before achieving true quantum advantage. With rapid quantum hardware development, continuous performance monitoring and evaluation will be important research directions in this field.