TL;DR
This paper establishes a universal upper bound on the transition amplitudes of bosons in any linear optical network. This bound proves that computational decision problems encoded in linear optics can be solved efficiently by classical computers, settling a long-standing open question and implying that linear optical quantum computers do not offer a computational advantage for these specific problems.
What Problem Does This Paper Address?
Linear optical networks, using components like beam splitters and phase shifters, are a promising platform for quantum information processing and simulation. A key question in this field is whether these systems can perform computations that are intractable for classical computers, a concept known as quantum supremacy. While boson sampling has been proposed as a task that might be hard for classical computers, this paper focuses on a related but distinct problem: decision problems encoded in linear optics. Specifically, the authors address the question of whether computational decision problems, when formulated as the determination of transition amplitudes in linear optical systems, can be solved efficiently by classical means. This is particularly relevant given the work by Aaronson and Hance, who posed an open problem regarding the efficient estimation of these amplitudes.
Methods
The core of the paper is the derivation of a universal upper bound on the absolute value of the transition amplitude between two Fock states in any linear optical network. This bound is expressed in terms of quantities derived from the initial and final photon number distributions. The authors employ a novel technique called "operator-to-number conversion," which allows them to transform complex polynomial functions of bosonic creation and annihilation operators into sums of complex numbers. This technique is crucial for developing a classical algorithm.
The proof involves several steps:
- Operator-to-number conversion: Expressing the transition amplitude as a sum over complex variables.
- Arithmetic-geometric inequality: Applying this inequality to bound the intermediate expressions.
- Bounding the norms: Utilizing the properties of unitary matrices and vector norms to arrive at the final bound.
This mathematical framework then leads to the development of a polynomial-time randomized algorithm for estimating these transition amplitudes with additive error.
Datasets
Not discussed in the paper. The paper focuses on theoretical derivations and algorithmic development rather than experimental implementation or evaluation on specific datasets.
Key Insights and Ideas
- Universal Bound: The discovery of a universal upper bound on boson transition amplitudes is a significant theoretical achievement. This bound applies to any physical linear optical network, providing a fundamental limit on the system's behavior.
- Classical Solvability of Decision Problems: The most impactful insight is that this bound directly implies the existence of a polynomial-time randomized algorithm for estimating transition amplitudes. This, in turn, means that decision problems encoded in linear optics (where the outcome is determined by the value of such an amplitude) can be solved efficiently by classical computers. This settles a major open question in the field.
- No Quantum Supremacy for These Problems: The paper demonstrates that, for decision problems formulated in this way, linear optical quantum computers do not offer a computational advantage over classical ones. This is a crucial clarification in the ongoing debate about quantum supremacy.
- Connection to Permanents: The transition amplitude is shown to be directly related to the permanent of a matrix representing the optical network. The derived bound thus also provides an upper bound on the permanent of such matrices.
- Generalization of Existing Results: The work extends previous results by Aaronson and Hance, which were limited to specific initial states, to arbitrary Fock product states.
Key Results
- Universal Upper Bound: The paper derives a universal upper bound for the transition amplitude $| \langle s_1 \dots s_m | U | t_1 \dots t_m \rangle | \le \min \{ v_s/v_t, v_t/v_s \}$, where $v_s$ and $v_t$ are quantities derived from the initial and final photon number distributions.
- Polynomial-Time Randomized Algorithm: The existence of a polynomial-time randomized algorithm for estimating boson transition amplitudes with additive error is proven. This algorithm is a solution to an open problem posed by Aaronson and Hance.
- Classical Efficiency for Decision Problems: Computational decision problems encoded in linear optics, when formulated using transition amplitudes, can be solved efficiently by classical computers.
- Absence of Exact Boson Bunching: The paper shows that for more than two photons, exact boson bunching (where all photons end up in the same mode) is not possible with linear optics, with probabilities decreasing rapidly.
Limitations and Future Work
- Additive vs. Multiplicative Error: The developed classical algorithm provides an additive error for estimating transition amplitudes. However, for tasks like boson sampling, which often require estimating amplitudes with multiplicative errors (to accurately reproduce a probability distribution), the algorithm would need to run for an exponentially long time. This distinction is important for understanding the limits of classical simulation of quantum sampling tasks.
- Scope of Decision Problems: The paper focuses on decision problems encoded in transition amplitudes. It acknowledges that other ways of encoding decision problems in linear optics might still be hard for classical computers, potentially involving exponentially many amplitudes.
- Future Work: The authors suggest that their framework can be applied to other areas, such as calculating many-body wave functions and S-matrices in quantum field theory. They also note that their bound can be used to generalize algorithms for approximating permanents of non-negative matrices. The connection between transition amplitudes and permanents opens avenues for further research in both quantum information and computational complexity.
Summary updated