Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Highly available systems

Theoretical foundations for creating a quantum photon computer

F.K. Aliev, A.P. Baranov, A.V. Ivakhin, A. V. Korol’kov, V.I. Rudskoy

Published Feb 2, 2024• 0 citations
Publisher

Abstract

Currently, significant results have emerged in the field of creation and application of quantum computers. We are talking about the Chinese quantum photonic computers Jiuzhang, Jiuzhang-2 (Jiuzhang 2.0), Jiuzhang-3 (Jiuzhang 3.0), which appeared respectively in 2020, 2021 and 2023, as well as the Canadian quantum photonic computer Borealis, which appeared in 2022. All these computers belong to the class of so-called quantum simulators – variants of quantum computers that solve one problem or a narrow class of problems. In addition to narrow specialization, quantum simulators have another important feature. In quantum simulators, controllable quantum objects simulate and effectively predict the behavior of real quantum systems. For example, in the quantum photonic computers Jiuzhang, Jiuzhang-2, Jiuzhang-3 and Borealis, the photons supplied to the inputs of these computers imitate the behavior of a “system of non-interacting identical bosons.” The Jiuzhang, Jiuzhang-2, Jiuzhang-3, and Borealis quantum simulators solve the problem of sampling bosons from a given distribution. Together they represent a significant scientific, technical and technological breakthrough in the development and creation of quantum computers. However, beyond what has been achieved, a number of important issues that are of interest both theoretically and for the field of practical applications remain unexamined. Among them are the following: about the architecture and composition of the elements of a quantum photonic computer, their number and connection diagram, as well as setting parameters that determine the required probability distribution from which boson samples are taken. The scientific problem addressed in the article is to obtain answers to the above questions by developing the theoretical foundations for creating a quantum photonic computer that solves the problem of sampling bosons from a given distribution in the most general case without restrictions on the distribution. The following results were obtained: the theoretical basis for the creation of a quantum photon computer (called in the article the Fuzuli boson sampler, briefly bsF) was developed that solves the problem of sampling bosons from a given distribution, for use as a quantum computing subsystem of a hybrid computing system to solve the problem of estimating matrix permanents; its constituent elements have been identified and studied, their numbers have been determined, and inter-element connection diagrams have been developed; an algorithm has been developed for tuning the bsF quantum photon computer to solve the problem of estimating matrix permanents; The functioning process of bsF is described. The article assumes that physically, in each cycle of operation of the bsF computer, the process of supplying photons to the inputs of the computer, their “movement” to the detectors, as well as the registration of photons by detectors is organized in such a way that the set of these photons imitates the behavior of a system of non-interacting identical bosons. Physical and engineering issues of ensuring such behavior of photons are not considered in this work. At the same time, the feasibility of such a possibility in practice (experimentally) is assumed to be undeniable. Examples confirming this position are the already created prototypes of quantum photonic computers in China (Jiuzhang, Jiuzhang-2, Jiuzhang-3) and in Canada (Borealis).

DOI
10.18127/j20729472-202402-01

Related papers

A classical algorithm to mimic quantum decisions

Mile Gu

In his famous 1982 lecture, Nobel laureate Richard Feynman seeded the idea of quantum computation. He reasoned that the amount of classical information required to describe a quantum system scaled exponentially with its size, and thus could not be efficiently simulated by a classical computer. Indeed, a fairly modest system of 100 quantum bits would already require more information to describe than all the present data storage on Earth [1]. Given this, there would likely be computational tasks that achieve quantum supremacy—impossible to perform practically without the aid of a quantum information processor. In the 37 intervening years, these initial ideas have solidified, as the discovery of a string of quantum algorithms—from efficient factoring of large numbers to simulating chemical reactions—fueled a race for quantum supremacy. Yet, even theoretically, conclusively deciding—if quantum supremacy has been achieved—is non-trivial. Judging what problems can be efficiently solved by classical computers turns out to be exceedingly hard in itself. Take factoring, for instance. It is really classical intractable, or is it merely that we have not yet found an efficient classical means to factor? As we better understood how quantum computers process information, we also got better at finding classical methods to simulate them. This in turn has inspired new efficient classical algorithms in surprising situations [2]. Prof. Man-Hong Yung, associate professor at the Southern University of Science and Technology, and colleagues provided a beautiful illustration of such a discovery. Their work has been published in the July 2019 issue of National Science Review [3]. It considers a specialized type of linear optical quantum processor. The input and output are encoded within an array of optical modes by adjusting their initial photon number. Computation is achieved by interfering with these modes via a network of beam splitters, such that photons in one mode are transferred to another. Such processors have captured scientific attention due to their ability to perform a task known as boson sampling. When each mode is initialized with a single photon, the output statistics allows efficient evaluation of the matrix permanent—a computational problem with very strong evidence for being classically intractable [4]. This, coupled with their relative ease of engineering, made this specialized type of quantum processor an ideal holy grail for demonstrating quantum supremacy. Given this, one may expect that classical computers can say little about what such processors will output. After all, the number of paths that a photon can take to reach one mode from another scales exponentially with the size of the beam-splitter network. One may therefore assume that it would take exponential resources to track these paths to determine the probability of a photon moving from mode A to mode B. However, Yung and colleagues showed that a classical algorithm can efficiently estimate the transition probabilities—as long as one allows for additive error. This result represents a significant generalization of prior results by Scott Aaronson, which considers the case where there exists at most one photon in each mode [5]. In contrast, Yung's solution works regardless of the number of photons encoded in each mode. The result not only benefits the simulation of bosonic interference, but also has strong consequences in computing. Suppose that we use such specialized quantum processors to make binary decisions. That is, depending on input, we feed in particular distributions of photons—and then decide to take a particular action depending on whether the probability of seeing x photons in a particular output is above some threshold. In such contexts, a classical algorithm that estimates this probability up to the bounded additive error is sufficient for making identical decisions as the quantum processer itself. As such, Yung's algorithm enables a classical computer to be able to efficiently mimic the decisions of its specialized linear optical counterpart. This will no doubt have important ramifications in the present race for quantum supremacy. Much present effort is spent on demonstrating quantum supremacy through boson sampling, and the results here indicate that we will need to introduce more sophisticated quantum architectures if we wish to demonstrate such supremacy in making the right decisions.

National Science Review•Jul 1, 2019•0 citations

The race for quantum supremacy: pushing the classical limit for photonic hardware

Nicolò Spagnolo, Fabio Sciarrino

The strong efforts towards the realization of scalable quantum computing are motivated by the promise of super-polynomial speed-up in several computational tasks. A first fundamental step in this route is to provide concrete evidence of ‘quantum supremacy'. Such a regime is obtained when a quantum device is capable of solving a specific problem faster than the best classical hardware. A serious attempt to provide a first demonstration of quantum speed-up with affordable resources is represented by boson sampling [1,2], a non-universal quantum-computational protocol exploiting indistinguishable single photons and linear optical devices. In this context, strong theoretical evidence has been reported that the interference pattern generated by a boson sampler is hard to simulate with classical resources, this pattern being related to the calculation of a hard-to-compute quantity known as a matrix permanent. Formal achievement of the regime of quantum supremacy will answer two very relevant questions: Are we able to benefit from the power of quantum mechanics or does there exist a fundamental reason why this achievement is forbidden? Once this regime has been achieved, are we able to certify the correct functioning of the quantum boson samplers or do we face an undecidability problem? Starting from these intriguing and promising theoretical results, an experimental race kicked off with the aim of reaching the quantum supremacy regime with boson sampling by employing a photonic platform [3]. A large amount of effort has been devoted to pushing the limits of current photonic systems [1], in order to significantly increase the size (number of photons and optical modes) that can be handled with a quantum device. In parallel to this quest for improved quantum performance, it is fundamental to benchmark the limits of a classical simulation of boson sampling. More specifically, in the race for quantum supremacy, what is the best possible classical simulation that can be performed? Such an analysis would be necessary to define the computational capacity possessed by such a classical agent to perform the task (see Fig. 1). In the race for quantum supremacy, a user who employs the best classical hardware and software, and a second agent who exploits a quantum device compete to solve the boson sampling task faster. In a recent article, Wu et al. [4] have provided a fundamental step to define and push the limits of a classical simulation of boson sampling. The authors have employed Tianhe-2, one of the world's most powerful super-computers, to perform such a task. More specifically, by using such high-performance computing hardware and by employing the fastest algorithm to date, Wu et al. have shown that calculating the permanent of a |$50 \times 50$| matrix can be performed in 100 min. Recent results [5] have shown that this computation corresponds to the classical hardness of drawing a 50-photon sample from a boson sampling distribution. The strong computational capacity of Tianhe-2 also allowed us to address the precision that the known fastest classical algorithms can reach in such a large-scale calculation. This latter aspect is indeed of fundamental importance, since any reliable classical computation must be accompanied by an appropriate error analysis. The study reported in Ref. [4] represents by far the largest calculation to date related to the classical simulation of boson sampling, whose relevance can be found in two different but related aspects. First, it raises the bar for any quantum implementation aimed at reaching quantum advantage, and provides a fundamental benchmark to which any photonic hardware must compare. This result suggests that a larger effort must be dedicated to pushing quantum technologies in this direction. Second, improved classical simulation also has important consequences in the context of boson sampling certification, i.e. the verification that a quantum device is correctly performing the required task. Indeed, first validation procedures in the quantum advantage regime must be assisted by powerful classical computational resources that, while requiring longer processing time than quantum hardware, will necessarily have to perform complex calculations.

National Science Review•Nov 6, 2018•11 citations

Quantum photonic computer technology for solving complex computational problems of high availability systems

F.K. Aliyev, E.G. Bukin, A. V. Korol’kov +1 more

We consider the problem of calculating the approximate value (estimate) of the permanent of a square matrix over the field of real numbers using a photonic quantum computer that sampling bosons from a given distribution. It is pointed out that it is possible to effectively solve this problem for the following three classes of matrices: symmetric matrices which eigenvalues do not exceed 1 in absolute value; orthogonal matrices; doubly stochastic matrices. For the last two classes, we are talking about evaluating the square of the permanent. The mathematical basis for solving the problem is the formula, which represents the permanent of the Hermitian matrix as the mathematical expectation of some random variable which values are equal to the products of the powers of the eigenvalues of the Hermitian matrix. And the corresponding probabilities with which these products are accepted as values of a random variable are also completely determined by the same Hermitian matrix. This circumstance allows using the methods of probability theory in order to solve the problem of permanent estimation.

Highly available systems•Jan 1, 2021•0 citations

Photonic implementation of boson sampling: a review

Daniel J. Brod, Ernesto F. Galvão, Andrea Crespi +3 more

Boson sampling is a computational problem that has recently been proposed as a candidate to obtain an unequivocal quantum computational advantage. The problem consists in sampling from the output distribution of indistinguishable bosons in a linear interferometer. There is strong evidence that such an experiment is hard to classically simulate, but it is naturally solved by dedicated photonic quantum hardware, comprising single photons, linear evolution, and photodetection. This prospect has stimulated much effort resulting in the experimental implementation of progressively larger devices. We review recent advances in photonic boson sampling, describing both the technological improvements achieved and the future challenges. We also discuss recent proposals and implementations of variants of the original problem, theoretical issues occurring when imperfections are considered, and advances in the development of suitable techniques for validation of boson sampling experiments. We conclude by discussing the future application of photonic boson sampling devices beyond the original theoretical scope.

Advanced Photonics•May 9, 2019•160 citations

Robust quantum computational advantage with programmable 3050-photon Gaussian boson sampling

Hua-Liang Liu, Su, Hao, Si-Qiu Gong +34 more

The creation of large-scale, high-fidelity quantum computers is not only a fundamental scientific endeavour in itself, but also provides increasingly robust proofs of quantum computational advantage (QCA) in the presence of unavoidable noise and the dynamic competition with classical algorithm improvements. To overcome the biggest challenge of photon-based QCA experiments, photon loss, we report new Gaussian boson sampling (GBS) experiments with 1024 high-efficiency squeezed states injected into a hybrid spatial-temporal encoded, 8176-mode, programmable photonic quantum processor, Jiuzhang 4.0, which produces up to 3050 photon detection events. Our experimental results outperform all classical spoofing algorithms, particularly the matrix product state (MPS) method, which was recently proposed to utilise photon loss to reduce the classical simulation complexity of GBS. Using the state-of-the-art MPS algorithm on the most powerful supercomputer EI Capitan, it would take > $10^{42}$ years to construct the required tensor network for simulation, while our Jiuzhang 4.0 quantum computer takes 25.6 $μ$s to produce a sample. This work establishes a new frontier of QCA and paves the way to fault-tolerant photonic quantum computing hardware.

arXiv:2508.09092•Aug 12, 2025•6 citations

Non-linear Boson Sampling

Nicolò Spagnolo, Daniel J. Brod, Ernesto F. Galvão +1 more

Abstract Boson Sampling is a task that is conjectured to be computationally hard for a classical computer, but which can be efficiently solved by linear-optical interferometers with Fock state inputs. Significant advances have been reported in the last few years, with demonstrations of small- and medium-scale devices, as well as implementations of variants such as Gaussian Boson Sampling. Besides the relevance of this class of computational models in the quest for unambiguous experimental demonstrations of quantum advantage, recent results have also proposed the first applications for hybrid quantum computing. Here, we introduce the adoption of non-linear photon–photon interactions in the Boson Sampling framework, and analyze the enhancement in complexity via an explicit linear-optical simulation scheme. By extending the computational expressivity of Boson Sampling, the introduction of non-linearities promises to disclose novel functionalities for this class of quantum devices. Hence, our results are expected to lead to new applications of near-term, restricted photonic quantum computers.

arXiv:2110.13788•npj Quantum Information•Jan 9, 2023•24 citations
Currently, significant results have emerged in the field of creation and application of quantum computers. We are talking about the Chinese quantum photonic computers Jiuzhang, Jiuzhang-2 (Jiuzhang 2.0), Jiuzhang-3 (Jiuzhang 3.0), which appeared respectively in 2020, 2021 and 2023, as well as the Canadian quantum photonic computer Borealis, which appeared in 2022. All these computers belong to the class of so-called quantum simulators – variants of quantum computers that solve one problem or a narrow class of problems. In addition to narrow specialization, quantum simulators have another important feature. In quantum simulators, controllable quantum objects simulate and effectively predict the behavior of real quantum systems. For example, in the quantum photonic computers Jiuzhang, Jiuzhang-2, Jiuzhang-3 and Borealis, the photons supplied to the inputs of these computers imitate the behavior of a “system of non-interacting identical bosons.” The Jiuzhang, Jiuzhang-2, Jiuzhang-3, and Borealis quantum simulators solve the problem of sampling bosons from a given distribution. Together they represent a significant scientific, technical and technological breakthrough in the development and creation of quantum computers. However, beyond what has been achieved, a number of important issues that are of interest both theoretically and for the field of practical applications remain unexamined. Among them are the following: about the architecture and composition of the elements of a quantum photonic computer, their number and connection diagram, as well as setting parameters that determine the required probability distribution from which boson samples are taken. The scientific problem addressed in the article is to obtain answers to the above questions by developing the theoretical foundations for creating a quantum photonic computer that solves the problem of sampling bosons from a given distribution in the most general case without restrictions on the distribution. The following results were obtained: the theoretical basis for the creation of a quantum photon computer (called in the article the Fuzuli boson sampler, briefly bsF) was developed that solves the problem of sampling bosons from a given distribution, for use as a quantum computing subsystem of a hybrid computing system to solve the problem of estimating matrix permanents; its constituent elements have been identified and studied, their numbers have been determined, and inter-element connection diagrams have been developed; an algorithm has been developed for tuning the bsF quantum photon computer to solve the problem of estimating matrix permanents; The functioning process of bsF is described. The article assumes that physically, in each cycle of operation of the bsF computer, the process of supplying photons to the inputs of the computer, their “movement” to the detectors, as well as the registration of photons by detectors is organized in such a way that the set of these photons imitates the behavior of a system of non-interacting identical bosons. Physical and engineering issues of ensuring such behavior of photons are not considered in this work. At the same time, the feasibility of such a possibility in practice (experimentally) is assumed to be undeniable. Examples confirming this position are the already created prototypes of quantum photonic computers in China (Jiuzhang, Jiuzhang-2, Jiuzhang-3) and in Canada (Borealis).
In his famous 1982 lecture, Nobel laureate Richard Feynman seeded the idea of quantum computation. He reasoned that the amount of classical information required to describe a quantum system scaled exponentially with its size, and thus could not be efficiently simulated by a classical computer. Indeed, a fairly modest system of 100 quantum bits would already require more information to describe than all the present data storage on Earth [1]. Given this, there would likely be computational tasks that achieve quantum supremacy—impossible to perform practically without the aid of a quantum information processor. In the 37 intervening years, these initial ideas have solidified, as the discovery of a string of quantum algorithms—from efficient factoring of large numbers to simulating chemical reactions—fueled a race for quantum supremacy. Yet, even theoretically, conclusively deciding—if quantum supremacy has been achieved—is non-trivial. Judging what problems can be efficiently solved by classical computers turns out to be exceedingly hard in itself. Take factoring, for instance. It is really classical intractable, or is it merely that we have not yet found an efficient classical means to factor? As we better understood how quantum computers process information, we also got better at finding classical methods to simulate them. This in turn has inspired new efficient classical algorithms in surprising situations [2]. Prof. Man-Hong Yung, associate professor at the Southern University of Science and Technology, and colleagues provided a beautiful illustration of such a discovery. Their work has been published in the July 2019 issue of National Science Review [3]. It considers a specialized type of linear optical quantum processor. The input and output are encoded within an array of optical modes by adjusting their initial photon number. Computation is achieved by interfering with these modes via a network of beam splitters, such that photons in one mode are transferred to another. Such processors have captured scientific attention due to their ability to perform a task known as boson sampling. When each mode is initialized with a single photon, the output statistics allows efficient evaluation of the matrix permanent—a computational problem with very strong evidence for being classically intractable [4]. This, coupled with their relative ease of engineering, made this specialized type of quantum processor an ideal holy grail for demonstrating quantum supremacy. Given this, one may expect that classical computers can say little about what such processors will output. After all, the number of paths that a photon can take to reach one mode from another scales exponentially with the size of the beam-splitter network. One may therefore assume that it would take exponential resources to track these paths to determine the probability of a photon moving from mode A to mode B. However, Yung and colleagues showed that a classical algorithm can efficiently estimate the transition probabilities—as long as one allows for additive error. This result represents a significant generalization of prior results by Scott Aaronson, which considers the case where there exists at most one photon in each mode [5]. In contrast, Yung's solution works regardless of the number of photons encoded in each mode. The result not only benefits the simulation of bosonic interference, but also has strong consequences in computing. Suppose that we use such specialized quantum processors to make binary decisions. That is, depending on input, we feed in particular distributions of photons—and then decide to take a particular action depending on whether the probability of seeing x photons in a particular output is above some threshold. In such contexts, a classical algorithm that estimates this probability up to the bounded additive error is sufficient for making identical decisions as the quantum processer itself. As such, Yung's algorithm enables a classical computer to be able to efficiently mimic the decisions of its specialized linear optical counterpart. This will no doubt have important ramifications in the present race for quantum supremacy. Much present effort is spent on demonstrating quantum supremacy through boson sampling, and the results here indicate that we will need to introduce more sophisticated quantum architectures if we wish to demonstrate such supremacy in making the right decisions.
The strong efforts towards the realization of scalable quantum computing are motivated by the promise of super-polynomial speed-up in several computational tasks. A first fundamental step in this route is to provide concrete evidence of ‘quantum supremacy'. Such a regime is obtained when a quantum device is capable of solving a specific problem faster than the best classical hardware. A serious attempt to provide a first demonstration of quantum speed-up with affordable resources is represented by boson sampling [1,2], a non-universal quantum-computational protocol exploiting indistinguishable single photons and linear optical devices. In this context, strong theoretical evidence has been reported that the interference pattern generated by a boson sampler is hard to simulate with classical resources, this pattern being related to the calculation of a hard-to-compute quantity known as a matrix permanent. Formal achievement of the regime of quantum supremacy will answer two very relevant questions: Are we able to benefit from the power of quantum mechanics or does there exist a fundamental reason why this achievement is forbidden? Once this regime has been achieved, are we able to certify the correct functioning of the quantum boson samplers or do we face an undecidability problem? Starting from these intriguing and promising theoretical results, an experimental race kicked off with the aim of reaching the quantum supremacy regime with boson sampling by employing a photonic platform [3]. A large amount of effort has been devoted to pushing the limits of current photonic systems [1], in order to significantly increase the size (number of photons and optical modes) that can be handled with a quantum device. In parallel to this quest for improved quantum performance, it is fundamental to benchmark the limits of a classical simulation of boson sampling. More specifically, in the race for quantum supremacy, what is the best possible classical simulation that can be performed? Such an analysis would be necessary to define the computational capacity possessed by such a classical agent to perform the task (see Fig. 1). In the race for quantum supremacy, a user who employs the best classical hardware and software, and a second agent who exploits a quantum device compete to solve the boson sampling task faster. In a recent article, Wu et al. [4] have provided a fundamental step to define and push the limits of a classical simulation of boson sampling. The authors have employed Tianhe-2, one of the world's most powerful super-computers, to perform such a task. More specifically, by using such high-performance computing hardware and by employing the fastest algorithm to date, Wu et al. have shown that calculating the permanent of a |50×5050 \times 5050×50| matrix can be performed in 100 min. Recent results [5] have shown that this computation corresponds to the classical hardness of drawing a 50-photon sample from a boson sampling distribution. The strong computational capacity of Tianhe-2 also allowed us to address the precision that the known fastest classical algorithms can reach in such a large-scale calculation. This latter aspect is indeed of fundamental importance, since any reliable classical computation must be accompanied by an appropriate error analysis. The study reported in Ref. [4] represents by far the largest calculation to date related to the classical simulation of boson sampling, whose relevance can be found in two different but related aspects. First, it raises the bar for any quantum implementation aimed at reaching quantum advantage, and provides a fundamental benchmark to which any photonic hardware must compare. This result suggests that a larger effort must be dedicated to pushing quantum technologies in this direction. Second, improved classical simulation also has important consequences in the context of boson sampling certification, i.e. the verification that a quantum device is correctly performing the required task. Indeed, first validation procedures in the quantum advantage regime must be assisted by powerful classical computational resources that, while requiring longer processing time than quantum hardware, will necessarily have to perform complex calculations.
We consider the problem of calculating the approximate value (estimate) of the permanent of a square matrix over the field of real numbers using a photonic quantum computer that sampling bosons from a given distribution. It is pointed out that it is possible to effectively solve this problem for the following three classes of matrices: symmetric matrices which eigenvalues do not exceed 1 in absolute value; orthogonal matrices; doubly stochastic matrices. For the last two classes, we are talking about evaluating the square of the permanent. The mathematical basis for solving the problem is the formula, which represents the permanent of the Hermitian matrix as the mathematical expectation of some random variable which values are equal to the products of the powers of the eigenvalues of the Hermitian matrix. And the corresponding probabilities with which these products are accepted as values of a random variable are also completely determined by the same Hermitian matrix. This circumstance allows using the methods of probability theory in order to solve the problem of permanent estimation.
Boson sampling is a computational problem that has recently been proposed as a candidate to obtain an unequivocal quantum computational advantage. The problem consists in sampling from the output distribution of indistinguishable bosons in a linear interferometer. There is strong evidence that such an experiment is hard to classically simulate, but it is naturally solved by dedicated photonic quantum hardware, comprising single photons, linear evolution, and photodetection. This prospect has stimulated much effort resulting in the experimental implementation of progressively larger devices. We review recent advances in photonic boson sampling, describing both the technological improvements achieved and the future challenges. We also discuss recent proposals and implementations of variants of the original problem, theoretical issues occurring when imperfections are considered, and advances in the development of suitable techniques for validation of boson sampling experiments. We conclude by discussing the future application of photonic boson sampling devices beyond the original theoretical scope.
The creation of large-scale, high-fidelity quantum computers is not only a fundamental scientific endeavour in itself, but also provides increasingly robust proofs of quantum computational advantage (QCA) in the presence of unavoidable noise and the dynamic competition with classical algorithm improvements. To overcome the biggest challenge of photon-based QCA experiments, photon loss, we report new Gaussian boson sampling (GBS) experiments with 1024 high-efficiency squeezed states injected into a hybrid spatial-temporal encoded, 8176-mode, programmable photonic quantum processor, Jiuzhang 4.0, which produces up to 3050 photon detection events. Our experimental results outperform all classical spoofing algorithms, particularly the matrix product state (MPS) method, which was recently proposed to utilise photon loss to reduce the classical simulation complexity of GBS. Using the state-of-the-art MPS algorithm on the most powerful supercomputer EI Capitan, it would take > 104210^{42}1042 years to construct the required tensor network for simulation, while our Jiuzhang 4.0 quantum computer takes 25.6 μμμs to produce a sample. This work establishes a new frontier of QCA and paves the way to fault-tolerant photonic quantum computing hardware.
Abstract Boson Sampling is a task that is conjectured to be computationally hard for a classical computer, but which can be efficiently solved by linear-optical interferometers with Fock state inputs. Significant advances have been reported in the last few years, with demonstrations of small- and medium-scale devices, as well as implementations of variants such as Gaussian Boson Sampling. Besides the relevance of this class of computational models in the quest for unambiguous experimental demonstrations of quantum advantage, recent results have also proposed the first applications for hybrid quantum computing. Here, we introduce the adoption of non-linear photon–photon interactions in the Boson Sampling framework, and analyze the enhancement in complexity via an explicit linear-optical simulation scheme. By extending the computational expressivity of Boson Sampling, the introduction of non-linearities promises to disclose novel functionalities for this class of quantum devices. Hence, our results are expected to lead to new applications of near-term, restricted photonic quantum computers.