Solving graph problems with single-photons and linear optics

• URL: http://arxiv.org/abs/2301.09594v2
• Date: Mon, 14 Aug 2023 17:15:13 GMT
• Title: Solving graph problems with single-photons and linear optics
• Authors: Rawad Mezher, Ana Filipa Carvalho, Shane Mansfield
• Abstract summary: We show how to efficiently encode a bounded $n times n$ matrix $A$ into a linear optical circuit with $2n$ modes. A photonic quantum processor consisting of single-photon sources, a linear optical circuit encoding $A$, and single-photon detectors can solve a range of graph problems.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: An important challenge for current and near-term quantum devices is finding useful tasks that can be preformed on them. We first show how to efficiently encode a bounded $n \times n$ matrix $A$ into a linear optical circuit with $2n$ modes. We then apply this encoding to the case where $A$ is a matrix containing information about a graph $G$. We show that a photonic quantum processor consisting of single-photon sources, a linear optical circuit encoding $A$, and single-photon detectors can solve a range of graph problems including finding the number of perfect matchings of bipartite graphs, computing permanental polynomials, determining whether two graphs are isomorphic, and the $k$-densest subgraph problem. We also propose pre-processing methods to boost the probabilities of observing the relevant detection events and thus improve performance. Finally we present both numerical simulations and implementations on Quandela's Ascella photonic quantum processor to validate our findings.

Related papers

• Linear Transformer Topological Masking with Graph Random Features [52.717865653036796]
  We show how to parameterise topological masks as a learnable function of a weighted adjacency matrix. Our efficient masking algorithms provide strong performance gains for tasks on image and point cloud data.
  arXiv  Detail & Related papers  (2024-10-04T14:24:06Z)
• Supervised binary classification of small-scale digit images and weighted graphs with a trapped-ion quantum processor [56.089799129458875]
  We present the results of benchmarking a quantum processor based on trapped $171$Yb$+$ ions.<n>We perform a supervised binary classification on two types of datasets: small binary digit images and weighted graphs with a ring topology.
  arXiv  Detail & Related papers  (2024-06-17T18:20:51Z)
• Automatically Identifying Local and Global Circuits with Linear Computation Graphs [45.760716193942685]
  We introduce our circuit discovery pipeline with Sparse Autoencoders (SAEs) and a variant called Transcoders. Our methods do not require linear approximation to compute the causal effect of each node. We analyze three kinds of circuits in GPT-2 Small: bracket, induction, and Indirect Object Identification circuits.
  arXiv  Detail & Related papers  (2024-05-22T17:50:04Z)
• A linear photonic swap test circuit for quantum kernel estimation [0.0]
  photonic swap test circuit successfully encodes two qubits and estimates their scalar product with a measured root mean square error smaller than 0.05. This result paves the way for the development of integrated photonic architectures capable of performing Quantum Machine Learning tasks with robust devices operating at room temperature.
  arXiv  Detail & Related papers  (2024-02-27T22:34:14Z)
• A Complete Graphical Language for Linear Optical Circuits with Finite-Photon-Number Sources and Detectors [0.0]
  We introduce the $textbfLO_fi$-calculus, a graphical language to reason on the infinite-dimensional bosonic Fock space. We present an equational theory that we prove to be complete: two $textbfLO_fi$-circuits represent the same quantum process.
  arXiv  Detail & Related papers  (2024-02-27T17:08:47Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• On sampling determinantal and Pfaffian point processes on a quantum computer [49.1574468325115]
  DPPs were introduced by Macchi as a model in quantum optics the 1970s. Most applications require sampling from a DPP, and given their quantum origin, it is natural to wonder whether sampling a DPP on a classical computer is easier than on a classical one. Vanilla sampling consists in two steps, of respective costs $mathcalO(N3)$ and $mathcalO(Nr2)$ operations on a classical computer, where $r$ is the rank of the kernel matrix.
  arXiv  Detail & Related papers  (2023-05-25T08:43:11Z)
• Efficient quantum linear solver algorithm with detailed running costs [0.0]
  We introduce a quantum linear solver algorithm combining ideasdiabatic quantum computing with filtering techniques based on quantum signal processing. Our protocol reduces the cost of quantum linear solvers over state-of-the-art close to an order of magnitude for early implementations.
  arXiv  Detail & Related papers  (2023-05-19T00:07:32Z)
• A Quadratic Speedup in the Optimization of Noisy Quantum Optical Circuits [5.074606924176912]
  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.
  arXiv  Detail & Related papers  (2023-03-15T18:51:36Z)
• Batch-efficient EigenDecomposition for Small and Medium Matrices [65.67315418971688]
  EigenDecomposition (ED) is at the heart of many computer vision algorithms and applications. We propose a QR-based ED method dedicated to the application scenarios of computer vision.
  arXiv  Detail & Related papers  (2022-07-09T09:14:12Z)
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
  Matching problems on 3D shapes and images are frequently formulated as quadratic assignment problems (QAPs) with permutation matrix constraints, which are NP-hard. We propose several reformulations of QAPs as unconstrained problems suitable for efficient execution on quantum hardware. The proposed algorithm has the potential to scale to higher dimensions on future quantum computing architectures.
  arXiv  Detail & Related papers  (2021-07-08T17:59:55Z)
• Quantum algorithms for spectral sums [50.045011844765185]
  We propose new quantum algorithms for estimating spectral sums of positive semi-definite (PSD) matrices. We show how the algorithms and techniques used in this work can be applied to three problems in spectral graph theory.
  arXiv  Detail & Related papers  (2020-11-12T16:29:45Z)
• Quantum verification of NP problems with single photons and linear optics [14.092977584342378]
  Quantum verification algorithms encode the solution into quantum bits rather than classical bit strings. By using tunable optical setups, we efficiently verify satisfiable and unsatisfiable SAT instances. Our results open an essentially new route towards quantum advantages and extend the computational capability of optical quantum computing.
  arXiv  Detail & Related papers  (2020-08-12T17:37:22Z)
• On connectivity-dependent resource requirements for digital quantum simulation of $d$-level particles [0.703901004178046]
  We study the number of SWAP gates required to Trotterize commonly used quantum operators. Results are applicable in hardware co-design and in choosing efficient qudit encodings for a given set of near-term quantum hardware.
  arXiv  Detail & Related papers  (2020-05-26T22:28:51Z)

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.