A Quadratic Speedup in the Optimization of Noisy Quantum Optical
Circuits
- URL: http://arxiv.org/abs/2303.08879v3
- Date: Wed, 9 Aug 2023 08:00:32 GMT
- Title: A Quadratic Speedup in the Optimization of Noisy Quantum Optical
Circuits
- Authors: Robbe De Prins, Yuan Yao, Anuj Apte and Filippo M. Miatto
- Abstract summary: Linear optical quantum circuits with photon number resolving (PNR) detectors are used for both Gaussian Boson Sampling (GBS) and for the preparation of non-Gaussian states such as Gottesman-Kitaev-Preskill (GKP)
We introduce a family of algorithms that calculate detection probabilities, conditional states and their gradients with respect to circuit parametrizations.
These algorithms are implemented and ready to use in the open-source photonic optimization library MrMustard.
- Score: 5.074606924176912
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Linear optical quantum circuits with photon number resolving (PNR) detectors
are used for both Gaussian Boson Sampling (GBS) and for the preparation of
non-Gaussian states such as Gottesman-Kitaev-Preskill (GKP), cat and NOON
states. They are crucial in many schemes of quantum computing and quantum
metrology. Classically optimizing circuits with PNR detectors is challenging
due to their exponentially large Hilbert space, and quadratically more
challenging in the presence of decoherence as state vectors are replaced by
density matrices. To tackle this problem, we introduce a family of algorithms
that calculate detection probabilities, conditional states (as well as their
gradients with respect to circuit parametrizations) with a complexity that is
comparable to the noiseless case. As a consequence we can simulate and optimize
circuits with twice the number of modes as we could before, using the same
resources. More precisely, for an $M$-mode noisy circuit with detected modes
$D$ and undetected modes $U$, the complexity of our algorithm is $O(M^2
\prod_{i\in U} C_i^2 \prod_{i\in D} C_i)$, rather than $O(M^2 \prod_{i \in
D\cup U} C_i^2)$, where $C_i$ is the Fock cutoff of mode $i$. As a particular
case, our approach offers a full quadratic speedup for calculating detection
probabilities, as in that case all modes are detected. Finally, these
algorithms are implemented and ready to use in the open-source photonic
optimization library MrMustard.
Related papers
- Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP)
We generalize the SDP-inspired quantum algorithm to sum-of-squares.
Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
arXiv Detail & Related papers (2024-08-14T19:04:13Z) - Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
We consider the problem of learning an $varepsilon$-optimal policy in a general class of continuous-space Markov decision processes (MDPs) having smooth Bellman operators.
Key to our solution is a novel projection technique based on ideas from harmonic analysis.
Our result bridges the gap between two popular but conflicting perspectives on continuous-space MDPs.
arXiv Detail & Related papers (2024-05-10T09:58:47Z) - Fast Minimization of Expected Logarithmic Loss via Stochastic Dual
Averaging [8.990961435218544]
We propose a first-order algorithm named $B$-sample dual averaging with the logarithmic barrier.
For the Poisson inverse problem, our algorithm attains an $varepsilon$ solution in $smashtildeO(d3/varepsilon2)$ time.
When computing the maximum-likelihood estimate for quantum state tomography, our algorithm yields an $varepsilon$-optimal solution in $smashtildeO(d3/varepsilon2)$ time.
arXiv Detail & Related papers (2023-11-05T03:33:44Z) - Quantum Algorithms for Sampling Log-Concave Distributions and Estimating
Normalizing Constants [8.453228628258778]
We develop quantum algorithms for sampling logconcave distributions and for estimating their normalizing constants.
We exploit quantum analogs of the Monte Carlo method and quantum walks.
We also prove a $1/epsilon1-o(1)$ quantum lower bound for estimating normalizing constants.
arXiv Detail & Related papers (2022-10-12T19:10:43Z) - Digital-analog co-design of the Harrow-Hassidim-Lloyd algorithm [0.0]
Harrow-Hassidim-Lloyd quantum algorithm was proposed to solve linear systems of equations $Avecx = vecb$.
There is not an explicit quantum circuit for the subroutine which maps the inverse of the problem matrix $A$ into an ancillary qubit.
We present a co-designed quantum processor which reduces the depth of the algorithm.
arXiv Detail & Related papers (2022-07-27T13:58:13Z) - Quantum Goemans-Williamson Algorithm with the Hadamard Test and
Approximate Amplitude Constraints [62.72309460291971]
We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits.
Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit.
We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
arXiv Detail & Related papers (2022-06-30T03:15:23Z) - Random quantum circuits transform local noise into global white noise [118.18170052022323]
We study the distribution over measurement outcomes of noisy random quantum circuits in the low-fidelity regime.
For local noise that is sufficiently weak and unital, correlations (measured by the linear cross-entropy benchmark) between the output distribution $p_textnoisy$ of a generic noisy circuit instance shrink exponentially.
If the noise is incoherent, the output distribution approaches the uniform distribution $p_textunif$ at precisely the same rate.
arXiv Detail & Related papers (2021-11-29T19:26:28Z) - Quantum-classical algorithms for skewed linear systems with optimized
Hadamard test [10.386115383285288]
We discuss hybrid quantum-classical algorithms for skewed linear systems for over-determined and under-determined cases.
Our input model is such that the columns or rows of the matrix defining the linear system are given via quantum circuits of poly-logarithmic depth.
We present an algorithm for the special case of a factorized linear system with run time poly-logarithmic in the respective dimensions.
arXiv Detail & Related papers (2020-09-28T12:59:27Z) - Enhancing the Quantum Linear Systems Algorithm using Richardson
Extrapolation [0.8057006406834467]
We present a quantum algorithm to solve systems of linear equations of the form $Amathbfx=mathbfb$.
The algorithm achieves an exponential improvement with respect to $N$ over classical methods.
arXiv Detail & Related papers (2020-09-09T18:00:09Z) - Hardness of Random Optimization Problems for Boolean Circuits,
Low-Degree Polynomials, and Langevin Dynamics [78.46689176407936]
We show that families of algorithms fail to produce nearly optimal solutions with high probability.
For the case of Boolean circuits, our results improve the state-of-the-art bounds known in circuit complexity theory.
arXiv Detail & Related papers (2020-04-25T05:45:59Z) - Quantum Algorithms for Simulating the Lattice Schwinger Model [63.18141027763459]
We give scalable, explicit digital quantum algorithms to simulate the lattice Schwinger model in both NISQ and fault-tolerant settings.
In lattice units, we find a Schwinger model on $N/2$ physical sites with coupling constant $x-1/2$ and electric field cutoff $x-1/2Lambda$.
We estimate observables which we cost in both the NISQ and fault-tolerant settings by assuming a simple target observable---the mean pair density.
arXiv Detail & Related papers (2020-02-25T19:18:36Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.