skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.


Title: Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints
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 only n + 1 qubits, a constant number of circuit preparations, and poly ( n ) expectation values in order to approximately solve semidefinite programs with up to N = 2 n variables and M O ( N ) 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 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
PAR ID:
10515580
Author(s) / Creator(s):
; ; ;
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
  1. 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
  2. Abstract A test of lepton flavor universality in B ± K ± μ + μ and B ± K ± e + e decays, as well as a measurement of differential and integrated branching fractions of a nonresonant B ± K ± μ + μ decay are presented. The analysis is made possible by a dedicated data set of proton-proton collisions at s = 13 TeV 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 B ( B ± K ± μ + μ ) to B ( B ± K ± e + e ) is determined from the measured double ratio R ( K ) of these decays to the respective branching fractions of the B ± J / ψ K ± with J / ψ μ + μ and e + e decays, which allow for significant cancellation of systematic uncertainties. The ratio R ( K ) is measured in the range 1.1 < q 2 < 6.0 GeV 2 , whereqis the invariant mass of the lepton pair, and is found to be R ( K ) = 0.78 0.23 + 0.47 , in agreement with the standard model expectation R ( K ) 1 . This measurement is limited by the statistical precision of the electron channel. The integrated branching fraction in the sameq2range, B ( B ± K ± μ + μ ) = ( 12.42 ± 0.68 ) × 10 8 , is consistent with the present world-average value and has a comparable precision. 
    more » « less
  3. A search is performed for charged-lepton flavor violating processes in top quark ( t ) production and decay. The data were collected by the CMS experiment from proton-proton collisions at a center-of-mass energy of 13 TeV and correspond to an integrated luminosity of 138 fb 1 . The selected events are required to contain one opposite-sign electron-muon pair, a third charged lepton (electron or muon), and at least one jet of which no more than one is associated with a bottom quark. Boosted decision trees are used to distinguish signal from background, exploiting differences in the kinematics of the final states particles. The data are consistent with the standard model expectation. Upper limits at 95% confidence level are placed in the context of effective field theory on the Wilson coefficients, which range between 0.024 0.424 TeV 2 depending on the flavor of the associated light quark and the Lorentz structure of the interaction. These limits are converted to upper limits on branching fractions involving up (charm) quarks, t e μ u ( t e μ c ), of 0.032 ( 0.498 ) × 10 6 , 0.022 ( 0.369 ) × 10 6 , and 0.012 ( 0.216 ) × 10 6 for tensorlike, vectorlike, and scalarlike interactions, respectively. 
    more » « less
  4. We report measurements of time-dependent C P asymmetries in B 0 K S 0 π 0 γ decays based on a data sample of ( 388 ± 6 ) × 10 6 B B ¯ events collected at the ϒ ( 4 S ) resonance with the Belle II detector. The Belle II experiment operates at the SuperKEKB asymmetric-energy e + e collider. We measure decay-time distributions to determine C P -violating parameters S and C . We determine these parameters for two ranges of K S 0 π 0 invariant mass: m ( K S 0 π 0 ) ( 0.8 , 1.0 ) GeV / c 2 , which is dominated by B 0 K * 0 ( K S 0 π 0 ) γ decays, and a complementary region m ( K S 0 π 0 ) ( 0.6 , 0.8 ) ( 1.0 , 1.8 ) GeV / c 2 . Our results have improved precision as compared to previous measurements and are consistent with theory predictions. Published by the American Physical Society2025 
    more » « less
  5. K + K pairs may be produced in photonuclear collisions, either from the decays of photoproduced ϕ ( 1020 ) mesons or directly as nonresonant K + K pairs. Measurements of K + K photoproduction probe the couplings between the ϕ ( 1020 ) and 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 of K + K pairs on lead ions in ultraperipheral collisions using the ALICE detector, including the first investigation of direct K + K production. There is significant K + K production at low transverse momentum, consistent with coherent photoproduction on lead targets. In the mass range 1.1 < M K K < 1.4 GeV / c 2 above the ϕ ( 1020 ) resonance, for rapidity | y K K | < 0.8 and p T , K K < 0.1 GeV / c , the measured coherent photoproduction cross section is d σ / d y = 3.37 ± 0.61 ( stat ) ± 0.15 ( syst ) mb . The center-of-mass energy per nucleon of the photon-nucleus (Pb) system W γ Pb , n ranges from 33 to 188 GeV, far higher than previous measurements on heavy-nucleus targets. The cross section is larger than expected for ϕ ( 1020 ) photoproduction alone. The mass spectrum is fit to a cocktail consisting of ϕ ( 1020 ) decays, direct K + K photoproduction, and interference between the two. The confidence regions for the amplitude and relative phase angle for direct K + K photoproduction are presented. © 2024 CERN, for the ALICE Collaboration2024CERN 
    more » « less