Table of Contents

1. Introduction
2. What Are Restricted Quantum Models?
3. Motivation: Why Study Non-Universal Models?
4. The IQP Model: Instantaneous Quantum Polynomial-Time
5. Structure of IQP Circuits
6. IQP Complexity Assumptions
7. Hardness of Simulating IQP Circuits
8. Relationship to BQP and Classical Classes
9. Commuting Quantum Circuits
10. Measurement-Based Interpretations of IQP
11. Examples of IQP Problems
12. Quantum Supremacy via IQP
13. Limitations of IQP and Physical Implementations
14. Comparison with Boson Sampling
15. Matchgate Circuits and Fermionic Models
16. DQC1: The One-Clean-Qubit Model
17. Clifford Circuits and Gottesman-Knill Theorem
18. QAOA as a Restricted Variational Model
19. Intermediate Models and Practical Quantum Advantage
20. Conclusion

1. Introduction

Restricted models of quantum computing aim to capture computational power achievable without full universality. These models are typically simpler, more experimentally realizable, and serve as platforms for demonstrating quantum advantage without needing fault-tolerant quantum computation.

2. What Are Restricted Quantum Models?

Restricted models are quantum computational frameworks that limit the types of gates, measurements, or initial states. Despite these constraints, many such models perform tasks believed to be classically intractable.

3. Motivation: Why Study Non-Universal Models?

Restricted models:

• Allow early experimental demonstrations of quantum power
• Provide complexity-theoretic insights
• Highlight the role of specific quantum features (e.g., entanglement, interference)
• Help identify minimal conditions for quantum advantage

4. The IQP Model: Instantaneous Quantum Polynomial-Time

IQP circuits consist of:

• A layer of Hadamard gates
• A sequence of commuting gates (usually diagonal in the Z-basis)
• A final layer of Hadamards followed by measurement
  All gates commute, and no adaptive operations are allowed during execution.

5. Structure of IQP Circuits

IQP circuits take the form:
\[
H^{\otimes n} D H^{\otimes n}
]
where \( D \) is a diagonal operator composed of gates like \( Z, CZ, CCZ \), all commuting. This structure eliminates timing constraints and supports parallel execution.

6. IQP Complexity Assumptions

It is conjectured that classically simulating the output of IQP circuits within total variation distance < 1/192 leads to collapse of the polynomial hierarchy. This underpins IQP’s complexity-theoretic importance.

7. Hardness of Simulating IQP Circuits

Under plausible assumptions, output distributions of IQP circuits are hard to simulate even approximately for classical computers. This offers a candidate path for quantum supremacy without universal quantum computers.

8. Relationship to BQP and Classical Classes

IQP ⊆ BQP (bounded-error quantum polynomial time), but is not known to contain BPP (classical probabilistic polytime). It captures a subclass of quantum computations with provable classical intractability in sampling.

9. Commuting Quantum Circuits

IQP circuits are a special case of commuting quantum circuits. Other examples include the commuting Hamiltonians studied in condensed matter and quantum phase transitions.

10. Measurement-Based Interpretations of IQP

IQP can be interpreted in measurement-based models (MBQC) on specific graph states. The non-adaptive measurement sequences map directly to IQP-style circuit evaluations.

11. Examples of IQP Problems

Problems well-suited for IQP include:

• Evaluation of partition functions of Ising models
• Sampling from certain parity check codes
• XOR games and stabilizer measurements

12. Quantum Supremacy via IQP

IQP circuits are strong candidates for early demonstrations of quantum supremacy because they are experimentally simpler and require fewer coherence-time resources than universal quantum computing.

13. Limitations of IQP and Physical Implementations

IQP circuits are not universal and cannot solve arbitrary problems like factoring. Implementing large-scale IQP circuits still requires precise gate control, low noise, and good measurement fidelity.

14. Comparison with Boson Sampling

Both IQP and boson sampling are non-universal sampling models. While IQP uses qubits and commuting gates, boson sampling uses photons and interferometers. Each model is hard to simulate classically under different assumptions.

15. Matchgate Circuits and Fermionic Models

Matchgate circuits are classically simulable when restricted, but become powerful when combined with limited extra resources. They model fermionic systems and connect to condensed matter physics.

16. DQC1: The One-Clean-Qubit Model

The DQC1 model uses only one pure qubit and many maximally mixed qubits. It solves some problems believed to be classically hard, such as estimating the trace of a unitary matrix.

17. Clifford Circuits and Gottesman-Knill Theorem

Clifford circuits are efficiently simulable on classical computers. They form the backbone of many restricted models and show that entanglement alone does not guarantee computational advantage.

18. QAOA as a Restricted Variational Model

The Quantum Approximate Optimization Algorithm (QAOA) is a low-depth variational model using alternating applications of problem and mixer Hamiltonians. It offers potential speedups for combinatorial optimization.

19. Intermediate Models and Practical Quantum Advantage

Models like IQP, DQC1, QAOA, and Boson Sampling demonstrate intermediate quantum power—between classical and fully universal quantum computers. They are key to achieving practical quantum advantage in the NISQ era.

20. Conclusion

IQP and other restricted quantum models provide fertile ground for exploring quantum complexity, supremacy, and experimental feasibility. They offer insight into which resources drive quantum power and how advantage may be demonstrated on near-term hardware.

Table of Contents

1. Introduction
2. What Are Sampling Problems?
3. Importance of Sampling in Complexity Theory
4. Classical vs Quantum Sampling Models
5. Boson Sampling: Basic Concept
6. Theoretical Foundation by Aaronson and Arkhipov
7. Matrix Permanents and Complexity
8. Gaussian Boson Sampling
9. Scattershot Boson Sampling
10. Experimental Requirements
11. Photon Sources and Indistinguishability
12. Interferometers and Optical Circuits
13. Detection and Readout Techniques
14. Early Experiments in Boson Sampling
15. Jiuzhang and Photonic Supremacy
16. Classical Hardness Assumptions
17. Verification and Validation Challenges
18. Noise, Errors, and Scalability
19. Alternative Sampling Models in Quantum Computing
20. Conclusion

1. Introduction

Sampling problems lie at the heart of demonstrating quantum advantage. Rather than solving a decision or search problem, sampling tasks ask for generating outcomes from specific probability distributions, which are believed to be intractable for classical computers under realistic constraints.

2. What Are Sampling Problems?

A sampling problem requires generating samples from a target distribution. Quantum sampling problems often involve output distributions of quantum circuits or physical systems, and are believed to be computationally hard to simulate classically.

3. Importance of Sampling in Complexity Theory

Sampling problems relate to complexity classes like BPP, BQP, and #P. Hardness of sampling connects to derandomization, collapse of the polynomial hierarchy, and the difficulty of computing matrix permanents.

4. Classical vs Quantum Sampling Models

Classical samplers are typically randomized algorithms, while quantum samplers use quantum interference, entanglement, and measurement collapse to produce samples from distributions not classically accessible in polynomial time.

5. Boson Sampling: Basic Concept

Boson sampling is a restricted model of quantum computation where indistinguishable photons are sent through a linear optical network and the output distribution is sampled via photon detectors. It’s not universal for quantum computing but believed to be hard to simulate classically.

6. Theoretical Foundation by Aaronson and Arkhipov

In 2011, Aaronson and Arkhipov showed that exact boson sampling with 50+ photons would be classically intractable under standard complexity assumptions. They linked the output probabilities to matrix permanents, a #P-hard problem.

7. Matrix Permanents and Complexity

The probability amplitude for a given boson sampling output is proportional to the permanent of a submatrix of the unitary matrix describing the interferometer. Computing matrix permanents is #P-complete, making even approximate simulation difficult.

8. Gaussian Boson Sampling

An extension of standard boson sampling, this method uses Gaussian input states (e.g., squeezed vacuum states) and measures correlation functions of photon-number outcomes. It has different computational properties but is also classically hard.

9. Scattershot Boson Sampling

Scattershot boson sampling increases experimental feasibility by using many potential photon sources and selecting only those that fire simultaneously. It helps bypass the challenge of deterministic single-photon generation.

10. Experimental Requirements

Key components include:

• High-fidelity indistinguishable single-photon sources
• Lossless and stable interferometers
• Photon-number-resolving detectors
• Synchronized triggering and measurement systems

11. Photon Sources and Indistinguishability

Photons must be spectrally, temporally, and spatially indistinguishable. Spontaneous parametric down-conversion (SPDC) is widely used but probabilistic. Quantum dots offer deterministic alternatives.

12. Interferometers and Optical Circuits

Interferometers implement the linear optical transformations. These must be stable, low-loss, and capable of implementing Haar-random unitaries for general-purpose sampling.

13. Detection and Readout Techniques

Efficient detection requires:

• Number-resolving photon detectors (e.g., TES, SNSPDs)
• Low dark count rates
• Fast timing resolution
  Readout speed and reliability are crucial for sampling fidelity.

14. Early Experiments in Boson Sampling

Initial boson sampling demonstrations used 3–5 photons in integrated photonic chips. These were proof-of-concept but lacked scalability. Gradual improvements led to higher photon counts and better indistinguishability.

15. Jiuzhang and Photonic Supremacy

China’s Jiuzhang photonic quantum computer achieved Gaussian boson sampling with up to 144 modes and 76 photons, claiming quantum supremacy. The sampling task was estimated to be infeasible on classical supercomputers.

16. Classical Hardness Assumptions

Boson sampling’s hardness depends on assumptions like:

• The permanent-of-Gaussians conjecture
• Anti-concentration of output probabilities
• No collapse of the polynomial hierarchy
  Violations of these could weaken its complexity foundations.

17. Verification and Validation Challenges

Unlike decision problems, verifying the correctness of quantum samples is hard. Techniques include cross-entropy benchmarking, likelihood estimation, and comparing with classical sub-simulations.

18. Noise, Errors, and Scalability

Photon loss, mode mismatch, and detector errors degrade sampling fidelity. As photon number increases, maintaining indistinguishability and optical circuit quality becomes increasingly challenging.

19. Alternative Sampling Models in Quantum Computing

Other models include:

• IQP (Instantaneous Quantum Polynomial-time)
• Random circuit sampling
• QAOA sampling
  These offer different trade-offs between theoretical guarantees and experimental accessibility.

20. Conclusion

Boson sampling represents a powerful but specialized method for demonstrating quantum computational advantage. While limited in general-purpose computing, it advances our understanding of quantum complexity and sets benchmarks for photonic quantum technologies.

Table of Contents

1. Introduction
2. What Is Quantum Supremacy?
3. Early Theoretical Proposals
4. Google’s Sycamore Experiment
5. Random Circuit Sampling Explained
6. Sycamore’s Hardware and Architecture
7. Verification Methods and Cross-Entropy Benchmarking
8. IBM’s Response and Classical Simulation Claims
9. Other Quantum Supremacy Proposals
10. BosonSampling and Photonic Supremacy
11. Quantum Supremacy with IQP and QAOA Circuits
12. Chinese Photonic Experiments: Jiuzhang
13. Role of Noise in Supremacy Claims
14. Error Correction and Experimental Limitations
15. Classical Simulation Catch-Up
16. Skepticism and Peer Review of Supremacy Claims
17. Practical vs Theoretical Supremacy
18. Supremacy Beyond Sampling: Future Targets
19. Implications for Quantum Computing Roadmaps
20. Conclusion

1. Introduction

Quantum supremacy refers to the experimental demonstration that a quantum computer can solve a problem significantly faster than the best-known classical computer. It marks a pivotal moment in the field, proving quantum hardware has crossed a crucial threshold.

2. What Is Quantum Supremacy?

Originally coined by John Preskill, quantum supremacy is achieved when a quantum device performs a computational task that is infeasible for classical machines within reasonable time and resources—even if the task has no practical use.

3. Early Theoretical Proposals

Schemes for demonstrating supremacy include:

• BosonSampling (Aaronson & Arkhipov)
• IQP circuits
• Random circuit sampling
  Each aimed to find classically hard problems solvable on near-term quantum devices.

4. Google’s Sycamore Experiment

In 2019, Google announced that its 53-qubit Sycamore processor performed a random sampling task in ~200 seconds, which would take the best classical supercomputers (at the time) ~10,000 years.

5. Random Circuit Sampling Explained

The supremacy task involved sampling from the output distribution of a randomly generated quantum circuit—a problem known to be hard to simulate classically due to exponential state space growth and interference.

6. Sycamore’s Hardware and Architecture

The Sycamore chip features:

• 53 programmable superconducting qubits
• Tunable couplers
• Low error rates (~0.1–0.5%)
• Custom calibration and gate optimization for fidelity

7. Verification Methods and Cross-Entropy Benchmarking

Google used cross-entropy benchmarking to compare the output distribution with theoretical predictions for small circuits. The match provided evidence the quantum processor behaved as expected.

8. IBM’s Response and Classical Simulation Claims

IBM challenged Google’s supremacy claim, arguing that classical supercomputers with sufficient memory and smarter algorithms could simulate the same task in a few days, not millennia.

9. Other Quantum Supremacy Proposals

Alternative supremacy tasks include:

• Random circuit sampling on trapped ions
• BosonSampling on photonic hardware
• Low-depth IQP and QAOA circuits for niche combinatorial problems

10. BosonSampling and Photonic Supremacy

BosonSampling involves sending indistinguishable photons through a linear optical network and sampling output configurations. Jiuzhang (2020) from China reported supremacy using this method, achieving exponential speedups in sampling.

11. Quantum Supremacy with IQP and QAOA Circuits

IQP (Instantaneous Quantum Polynomial-time) and QAOA circuits are alternatives that promise supremacy under different assumptions. These use restricted gate sets and can target combinatorial or optimization problems.

12. Chinese Photonic Experiments: Jiuzhang

In 2020 and 2021, China’s Jiuzhang processor demonstrated photonic quantum supremacy using Gaussian BosonSampling with up to 144 detected photons—far beyond classical simulation capabilities.

13. Role of Noise in Supremacy Claims

Supremacy demonstrations must show robustness to noise. Excessive noise could mean output distributions are classically simulable, thus invalidating supremacy. Verifying this remains an experimental challenge.

14. Error Correction and Experimental Limitations

Supremacy tasks often avoid full error correction. As qubit numbers grow, error accumulation becomes a bottleneck. Experiments are typically performed at the edge of circuit depth tolerable by device coherence.

15. Classical Simulation Catch-Up

Classical simulation techniques (tensor networks, cluster state methods) continue to improve. Each supremacy claim spurs efforts to close the classical gap, raising the bar for future demonstrations.

16. Skepticism and Peer Review of Supremacy Claims

The field has seen active debate, with scrutiny over whether supremacy was truly achieved. Concerns include benchmark relevance, verification trust, and hidden classical optimizations.

17. Practical vs Theoretical Supremacy

Most supremacy tasks are designed to be hard but not useful. Transitioning from theoretical to practical advantage (e.g., solving chemistry, optimization, or ML tasks) remains an ongoing goal.

18. Supremacy Beyond Sampling: Future Targets

Future targets for supremacy include:

• Linear systems (HHL)
• Quantum simulations of molecules
• Variational quantum optimization
  These could provide both practical value and theoretical proof of quantum advantage.

19. Implications for Quantum Computing Roadmaps

Quantum supremacy proves hardware viability, guiding investments and design strategies. It motivates scaling efforts and hybrid algorithm development for real-world use.

20. Conclusion

Quantum supremacy experiments showcase the unique potential of quantum processors. While challenges and debates persist, they have pushed the boundaries of computation and set a benchmark for the future of quantum advantage.