Quantum computing holds the promise of enabling algorithms that are beyond the reach of classical computation, hence demonstrating quantum computational advantage. However, current quantum devices face significant limitations, primarily due to the lack of error correction. In this context, the following question arises: can quantum computational advantage be demonstrated with today's noisy hardware? Recently, Gaussian boson sampling (GBS) has emerged as a leading candidate to achieve this milestone, due to its relative experimental feasibility. The first part of this thesis focuses on two central challenges associated with GBS. The first one is the impact of noise on the computational complexity of the task. Using a phase-space approach, we establish a necessary non-classicality condition that any experimental proof of quantum advantage must satisfy, and demonstrate that there exists a threshold temperature at which quantum sampling experiments become classically simulable. We then investigate the possibility of introducing higher-order non-linearities as a mean to enhance the protocol’s robustness against noise. Then, we turn our attention to the problem of validating a GBS experiment, and propose the use binned-detector probability distributions as a suitable quantity to perform efficient statistical validation. In the second part of the thesis, we present a novel approach to protect a quantum observable from a given noise model.We start by introducing the concept of quantum observables over time, an operator that jointly describes two observables at two distinct time points, and use the latter to establish a notion of time-reversal for non-unitary quantum channels with respect to a reference observable, enabling the systematic construction of recovery maps that preserve the latter. These recovery maps, although generally non-physical, can still be used in noiseless expectation value estimation tasks and can achieve optimal performance in terms of sampling overhead, outperforming known error mitigation protocols.
Quantum computing holds the promise of enabling algorithms that are beyond the reach of classical computation, hence demonstrating quantum computational advantage. However, current quantum devices face significant limitations, primarily due to the lack of error correction. In this context, the following question arises: can quantum computational advantage be demonstrated with today's noisy hardware? Recently, Gaussian boson sampling (GBS) has emerged as a leading candidate to achieve this milestone, due to its relative experimental feasibility. The first part of this thesis focuses on two central challenges associated with GBS. The first one is the impact of noise on the computational complexity of the task. Using a phase-space approach, we establish a necessary non-classicality condition that any experimental proof of quantum advantage must satisfy, and demonstrate that there exists a threshold temperature at which quantum sampling experiments become classically simulable. We then investigate the possibility of introducing higher-order non-linearities as a mean to enhance the protocol’s robustness against noise. Then, we turn our attention to the problem of validating a GBS experiment, and propose the use binned-detector probability distributions as a suitable quantity to perform efficient statistical validation. In the second part of the thesis, we present a novel approach to protect a quantum observable from a given noise model.We start by introducing the concept of quantum observables over time, an operator that jointly describes two observables at two distinct time points, and use the latter to establish a notion of time-reversal for non-unitary quantum channels with respect to a reference observable, enabling the systematic construction of recovery maps that preserve the latter. These recovery maps, although generally non-physical, can still be used in noiseless expectation value estimation tasks and can achieve optimal performance in terms of sampling overhead, outperforming known error mitigation protocols.
It remains questionable whether all physically realizable computational model can be simulated by currently available digital computer in an efficient manner. The theory of Quantum Mechanics offers an answer to this question through one of its branches that intersects with Computer Science, known as Quantum Computing. It claims that current computers, which is operating based on classical mechanics cannot efficiently simulate quantum mechanical process. Under this claim, a computer that is operating based on quantum mechanics holds more computational power than classical computers, promising a possibility to computationally solve problems that are classically intractable. To show that this claim holds, numerous quantum computational models have been proposed and analyzed through the lens of Computational Complexity Theory, providing a rigorous notion of efficiency. Models that are more feasible experimentally, although not necessarily universal, have also been of a particular interests given the numerous complicated challenges surrounding the experimental implementation of a universal quantum computer. One of this non-universal models is called Gaussian Boson Sampling (GBS), which embraces the methods of Quantum Optics by sampling the number of photon outputs from a linear optical network as a means to process quantum information. Compared to its prototype model, Boson Sampling, GBS is more experimentally feasible due to its method of generating photon that is based on the Continuous Variable (CV) paradigm of Quantum Information. Nevertheless as with Boson Sampling, it was also shown that classical simulation of GBS cannot be performed efficiently under some highly plausible conjectures. In the work presented in this thesis, we probe the complexity of classically constructing the probability distribution induced by GBS using the method of Quantum Homodyne Tomography. Instead of photon number measurement, this method further embraces the CV paradigm in the measurement of GBS by using Homodyne measurements that outputs real numbers. Sample data obtained from the measurement outcomes is then classically processed using Pattern Functions, which we use to approximate the probability distribution of GBS. A series of computer simulations that approximates some probability values of GBS are presented here, which shows that the number of samples needed to decrease the error of the approximation increases rapidly for more accurate approximation. We have derived a bound for the approximation error which can be achieved given that the sampled data satisfies a certain statistical property. This statistical property can eventually be satisfied as the number of Homodyne samples increases. Having shown another evidence for the complexity of approximating GBS using Homodyne Tomography, we further investigate the nature of the complexity of GBS by analyzing its classical-quantum computational boundary in the spectrum of amount of noise present in a GBS setup. In doing this, we built our discussions on the measure of non-classicality using the presence of negative values in the Quasi-probability distribution (QPD) representation of states of a quantum system. We then discuss existing results that shows the possibility of efficient classical simulation of a quantum computational model given a sufficient amount of noise. These results impose a necessary criteria of the minimum amount of noise that an experiment has to surpass in order for it to be impossible to simulate classically in an efficient manner. We extend this idea for GBS, where we propose a modified GBS where we consider noise in its measurements that opens a way for a possible formulation of a noise condition that a GBS experiment has to fulfill to rule out possible efficient classical simulation. To further probe the classical-quantum computational boundary, we also propose a different quantum computational model called the Photon-added Thermal State CV-Sampling (PATS CVS), which can be formulated similarly to our noisy GBS model. We then discuss existing results that analyzes the negativity of the QPD representation of a noisy Photon-added Thermal state (PATS), which constitutes the inputs for PATS CVS. Using the result that shows the quantum-classical transition in terms of the QPD negativity for a PATS state when the amount of noise changes, we discuss the potential of PATS CVS model as a possible avenue to further probe the transition between efficiently simulable and non-efficiently simulable quantum mechanical experiment.
Quantum computers solve intractable problems which classically require an exponentially long time to compute. With the development of large-scale experiments that claim quantum advantage, a vital issue has now emerged. What are the errors, and how do they affect the complexity of the problem solved? Large-scale Gaussian boson sampling (GBS) experiments give an example in which random numbers are generated. Despite classical hardness, these have computable benchmarks for checking data validity. While there are other quantum computing architectures, Gaussian boson sampling is uniquely testable at all scales. Several large, pioneering quantum computing (QC) experiments have been carried out to investigate quantum advantage. Here, we introduce a highly scalable but classical algorithm that can solve GBS approximately. Our numerical simulation of the output count data is closer to the exact solution than current experiments up to 1152 modes. This algorithm outperforms all previous classical, approximate algorithms and scales efficiently to larger experiments. Our results show that effects beyond losses can cause the errors that allow classical simulability. This work will lead to more precise algorithms and is a step towards understanding how QC quantum advantage is affected by the underlying physics.
Validation of quantum advantage claims in the context of Gaussian boson sampling (GBS) currently relies on providing evidence that the experimental samples genuinely follow their corresponding ground truth, i.e., the theoretical model of the experiment that includes all the possible losses that the experimenters can account for. This approach to verification has an important drawback: it is necessary to assume that the ground truth distributions are computationally hard to sample, that is, that they are sufficiently close to the distribution of the ideal, lossless experiment, for which there is evidence that sampling, either exactly or approximately, is a computationally hard task. This assumption, which cannot be easily confirmed, opens the door to classical algorithms that exploit the noise in the ground truth to efficiently simulate the experiments, thus undermining any quantum advantage claim. In this work, we argue that one can avoid this issue by validating GBS implementations using their corresponding ideal distributions directly. We explain how to use a modified version of the linear cross-entropy, a quantity that we call the LXE score, to find reference values that help us assess how close a given GBS implementation is to its corresponding ideal model. Finally, we analytically compute the score that would be obtained by a lossless GBS implementation. Published by the American Physical Society 2024
Learning problems involving quantum data are natural candidates for demonstrating an advantage in quantum machine learning. Recent results indicate that, for certain tasks and under noiseless conditions, coherent processing of quantum data outperforms fixed-measurement schemes followed by classical processing. It remained uncertain whether this performance gap persists at a finite scale, and in the presence of noise that is unavoidable with current quantum devices. In this work, we present simulations and analysis of the performance of existing hardware on a learning problem known to exhibit asymptotic advantage, now subjected to noisy quantum data. Comparing coherent quantum processing directly against fixed-measurement schemes, our results demonstrate a clear performance separation at a scale of just 30 to 40 noisy qubits. Already at this scale, the fundamental bottleneck is no longer classical computation but data acquisition; matching the noisy coherent protocol with measure-first strategies would still require months or even years of measurements. By systematically evaluating hardware constraints such as state preparation, gate errors, readout errors, connectivity, and coherence times, we provide evidence that a demonstration of such a strong learning advantage is accessible on near-term devices.
Exploiting the coherence and entanglement of quantum many-qubit states, quantum computing can significantly surpass classical algorithms, making it possible to factor large numbers, solve linear equations, simulate many-body quantum systems, etc., in a reasonable time. With the rapid development of quantum computing hardware, many attention has been drawn to explore how quantum computers could go beyond the limit of classical computation. Owing to the need of a universal fault-tolerant quantum computer for many existing quantum algorithms, such as Shor’s factoring algorithm, and considering the limit of near-term quantum devices with small qubit numbers and short coherence times, many recent works focused on the exploration of demonstrating quantum advantages using noisy intermediate-scaled quantum devices and shallow circuits, and hence some sampling problems have been proposed as the candidates for quantum advantage demonstration. This review summarizes quantum advantage problems that are realizable on current quantum hardware. We focus on two notable problems—random circuit simulation and boson sampling—and consider recent theoretical and experimental progresses. After the respective demonstrations of these two types of quantum advantages on superconducting and optical quantum platforms, we expect current and near-term quantum devices could be employed for demonstrating quantum advantages in general problems.
Boson sampling, a computational problem conjectured to be hard to simulate on a classical machine, is a promising candidate for an experimental demonstration of quantum advantage using bosons. However, inevitable experimental noise and imperfections, such as loss in the interferometer and random counts at the detectors, could challenge the sampling task from entering the regime where quantum advantage is achievable. In this work we introduce higher-order nonlinearities as a means to enhance the computational complexity of the problem and the protocol's robustness against noise, i.e., to increase the noise threshold that allows us to perform an efficient classical simulation of the problem. Using a phase-space method based on the negativity volume of the relevant quasiprobability distributions, we establish a necessary nonclassicality condition that any experimental proof of quantum advantage must satisfy. Our results indicate that the addition of single-mode Kerr nonlinearity at the input-state preparation level, while retaining a linear-optical evolution, makes the boson-sampling protocol more robust against noise and consequently relaxes the constraints on the noise parameters required to show quantum advantage.