Semidefinite programs are optimization methods with a wide array of applications, such as approximating difficult combinatorial problems. One such semidefinite program is the Goemans-Williamson algorithm, a popular integer relaxation technique. We introduce a variational quantum algorithm for the Goemans-Williamson algorithm that uses onlyqubits, a constant number of circuit preparations, andexpectation values in order to approximately solve semidefinite programs with up tovariables andconstraints. Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit, a technique known as the Hadamard Test. The Hadamard Test enables us to optimize the objective function by estimating only a single expectation value of the ancilla qubit, rather than separately estimating exponentially many expectation values. Similarly, we illustrate that the semidefinite programming constraints can be effectively enforced by implementing a second Hadamard Test, as well as imposing a polynomial number of Pauli string amplitude constraints. We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems, including MaxCut. Our method exceeds the performance of analogous classical methods on a diverse subset of well-studied MaxCut problems from the GSet library.
more » « less- Award ID(s):
- 2317134
- NSF-PAR ID:
- 10515580
- Publisher / Repository:
- Quantum
- Date Published:
- Journal Name:
- Quantum
- Volume:
- 7
- ISSN:
- 2521-327X
- Page Range / eLocation ID:
- 1057
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
Semidefinite programs are optimization methods with a wide array of applications, such as approximating difficult combinatorial problems. We introduce a variational quantum algorithm for semidefinite programs that uses only n qubits, a constant number of circuit preparations, and O(n2) expectation values in order to solve semidefinite programs with up to N=2n variables and M=2n constraints. Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit, a technique known as the Hadamard Test. The Hadamard Test enables us to optimize the objective function by estimating only a single expectation value of the ancilla qubit, rather than separately estimating exponentially many expectation values. Similarly, we illustrate that the semidefinite programming constraints can be effectively enforced by implementing a second Hadamard Test, as well as imposing ∼n2/2 Pauli string amplitude constraints. We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm, which is a useful approximation for various NP-hard problems, such as MaxCut. Our method exceeds the performance of analogous classical methods on a diverse subset of well-studied MaxCut problems from the GSet library.more » « less
-
Abstract A test of lepton flavor universality in
and decays, as well as a measurement of differential and integrated branching fractions of a nonresonant decay are presented. The analysis is made possible by a dedicated data set of proton-proton collisions at recorded in 2018, by the CMS experiment at the LHC, using a special high-rate data stream designed for collecting about 10 billion unbiased b hadron decays. The ratio of the branching fractions to is determined from the measured double ratio of these decays to the respective branching fractions of the with and decays, which allow for significant cancellation of systematic uncertainties. The ratio is measured in the range , whereq is the invariant mass of the lepton pair, and is found to be , in agreement with the standard model expectation . This measurement is limited by the statistical precision of the electron channel. The integrated branching fraction in the sameq 2range, , is consistent with the present world-average value and has a comparable precision. -
pairs may be produced in photonuclear collisions, either from the decays of photoproducedmesons or directly as nonresonantpairs. Measurements ofphotoproduction probe the couplings between theand charged kaons with photons and nuclear targets. The kaon-proton scattering occurs at energies far above those available elsewhere. We present the first measurement of coherent photoproduction ofpairs on lead ions in ultraperipheral collisions using the ALICE detector, including the first investigation of directproduction. There is significantproduction at low transverse momentum, consistent with coherent photoproduction on lead targets. In the mass rangeabove theresonance, for rapidityand, the measured coherent photoproduction cross section is. The center-of-mass energy per nucleon of the photon-nucleus (Pb) systemranges from 33 to 188 GeV, far higher than previous measurements on heavy-nucleus targets. The cross section is larger than expected forphotoproduction alone. The mass spectrum is fit to a cocktail consisting ofdecays, directphotoproduction, and interference between the two. The confidence regions for the amplitude and relative phase angle for directphotoproduction are presented.
© 2024 CERN, for the ALICE Collaboration 2024 CERN -
We search for the rare decayin asample of electron-positron collisions at theresonance collected with the Belle II detector at the SuperKEKB collider. We use the inclusive properties of the accompanyingmeson inevents to suppress background from other decays of the signalcandidate and light-quark pair production. We validate the measurement with an auxiliary analysis based on a conventional hadronic reconstruction of the accompanyingmeson. For background suppression, we exploit distinct signal features using machine learning methods tuned with simulated data. The signal-reconstruction efficiency and background suppression are validated through various control channels. The branching fraction is extracted in a maximum likelihood fit. Our inclusive and hadronic analyses yield consistent results for thebranching fraction ofand, respectively. Combining the results, we determine the branching fraction of the decayto be, providing the first evidence for this decay at 3.5 standard deviations. The combined result is 2.7 standard deviations above the standard model expectation.
Published by the American Physical Society 2024 -
The first observation of the decayand measurement of the branching ratio oftoare presented. Theandmesons are reconstructed using their dimuon decay modes. The results are based on proton-proton colliding beam data from the LHC collected by the CMS experiment atin 2016–2018, corresponding to an integrated luminosity of. The branching fraction ratio is measured to be, where the last uncertainty comes from the uncertainties in the branching fractions of the charmonium states. New measurements of thebaryon mass and natural width are also presented, using thefinal state, where thebaryon is reconstructed through the decays,,, and. Finally, the fraction ofbaryons produced fromdecays is determined.
© 2024 CERN, for the CMS Collaboration 2024 CERN