Laplace expansions and tree decompositions: polytime algorithm for shallow nearest-neighbour Boson Sampling

• URL: http://arxiv.org/abs/2412.18664v1
• Date: Tue, 24 Dec 2024 19:34:26 GMT
• Title: Laplace expansions and tree decompositions: polytime algorithm for shallow nearest-neighbour Boson Sampling
• Authors: Samo Novák, Raúl García-Patrón,
• Abstract summary: In a Boson Sampling quantum optical experiment we send $n$ individual photons into an $m$-mode interferometer and we measure the occupation pattern on the output. We exploit the fact that for a nearest-neighbour shallow circuit, i.e. depth depth $D = mathcalO(log m)$, one can adapt the algorithm by Cifuentes & Parrilo to exploit the sparsity of the shallow interferometer.
• Score: 0.30693357740321775
• License:
• Abstract: In a Boson Sampling quantum optical experiment we send $n$ individual photons into an $m$-mode interferometer and we measure the occupation pattern on the output. The statistics of this process depending on the permanent of a matrix representing the experiment, a #P-hard problem to compute, is the reason behind ideal and fully general Boson Sampling being hard to simulate on a classical computer. We exploit the fact that for a nearest-neighbour shallow circuit, i.e. depth $D = \mathcal{O}(\log m)$, one can adapt the algorithm by Clifford & Clifford (2018) to exploit the sparsity of the shallow interferometer using an algorithm by Cifuentes & Parrilo (2016) that can efficiently compute a permanent of a structured matrix from a tree decomposition. Our algorithm generates a sample from a shallow circuit in time $\mathcal{O}(n^22^\omega \omega^2) + \mathcal{O}(\omega n^3)$, where $\omega$ is the treewidth of the decomposition which satisfies $\omega \le 2D$ for nearest-neighbour shallow circuits. The key difference in our work with respect to previous work using similar methods is the reuse of the structure of the tree decomposition, allowing us to adapt the Laplace expansion used by Clifford & Clifford which removes a significant factor of $m$ from the running time, especially as $m>n^2$ is a requirement of the original Boson Sampling proposal.

Related papers

• 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)
• An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue Optimization Problems [76.2042837251496]
  We introduce two oblivious mirror descent algorithms based on a complementary composite setting. Remarkably, both algorithms work without prior knowledge of the Lipschitz constant or smoothness of the objective function. We show how to extend our framework to scale and demonstrate the efficiency and robustness of our methods on large scale semidefinite programs.
  arXiv  Detail & Related papers  (2023-06-30T08:34:29Z)
• Detection-Recovery Gap for Planted Dense Cycles [72.4451045270967]
  We consider a model where a dense cycle with expected bandwidth $n tau$ and edge density $p$ is planted in an ErdHos-R'enyi graph $G(n,q)$. We characterize the computational thresholds for the associated detection and recovery problems for the class of low-degree algorithms.
  arXiv  Detail & Related papers  (2023-02-13T22:51:07Z)
• ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
  We introduce a new tool for BFG convex optimization (SCO): a Reweighted Query (ReSQue) estimator for the gradient of a function convolved with a (Gaussian) probability density. We develop algorithms achieving state-of-the-art complexities for SCO in parallel and private settings.
  arXiv  Detail & Related papers  (2023-01-01T18:51:29Z)
• A Law of Robustness beyond Isoperimetry [84.33752026418045]
  We prove a Lipschitzness lower bound $Omega(sqrtn/p)$ of robustness of interpolating neural network parameters on arbitrary distributions. We then show the potential benefit of overparametrization for smooth data when $n=mathrmpoly(d)$. We disprove the potential existence of an $O(1)$-Lipschitz robust interpolating function when $n=exp(omega(d))$.
  arXiv  Detail & Related papers  (2022-02-23T16:10:23Z)
• Introducing the Expohedron for Efficient Pareto-optimal Fairness-Utility Amortizations in Repeated Rankings [9.066817876491053]
  We consider the problem of computing a sequence of rankings that maximizes consumer-side utility while minimizing producer-side individual unfairness of exposure. We introduce a geometrical object, a polytope that we call expohedron, whose points represent all achievable exposures of items for a Position Based Model. Our approach compares favorably to linear or quadratic programming baselines in terms of algorithmic complexity and empirical runtime. Our solution can be expressed as a distribution over only $n$ permutations, instead of the $(n-1)2 + 1$ achieved with BvN decompositions.
  arXiv  Detail & Related papers  (2022-02-07T14:43:35Z)
• How to simulate quantum measurement without computing marginals [3.222802562733787]
  We describe and analyze algorithms for classically computation measurement of an $n$-qubit quantum state $psi$ in the standard basis. Our algorithms reduce the sampling task to computing poly(n)$ amplitudes of $n$-qubit states.
  arXiv  Detail & Related papers  (2021-12-15T21:44:05Z)
• Fast simulation of planar Clifford circuits [0.0]
  A general quantum circuit can be simulated classically in exponential time. We show that treewidth and planarity can be exploited to improve Clifford circuit simulation.
  arXiv  Detail & Related papers  (2020-09-07T16:27:09Z)
• Faster classical Boson Sampling [0.15229257192293197]
  We present an algorithm for Boson Sampling whose average-case time complexity is much faster when $m$ is proportional to $n$. This result further increases the problem size needed to establish quantum computational supremacy via Boson Sampling.
  arXiv  Detail & Related papers  (2020-05-07T20:01:02Z)
• Maximizing Determinants under Matroid Constraints [69.25768526213689]
  We study the problem of finding a basis $S$ of $M$ such that $det(sum_i in Sv_i v_i v_itop)$ is maximized. This problem appears in a diverse set of areas such as experimental design, fair allocation of goods, network design, and machine learning.
  arXiv  Detail & Related papers  (2020-04-16T19:16:38Z)

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.