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
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 qubits, a constant number of circuit preparations, and expectation values in order to approximately solve semidefinite programs with up to variables and 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
- 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
-
-
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 , whereqis 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 sameq2range, , is consistent with the present world-average value and has a comparable precision.more » « less
-
A search is performed for charged-lepton flavor violating processes in top quark ( ) 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 . 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 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, ( ), of , , and for tensorlike, vectorlike, and scalarlike interactions, respectively.more » « less
-
We report measurements of time-dependent asymmetries in decays based on a data sample of events collected at the resonance with the Belle II detector. The Belle II experiment operates at the SuperKEKB asymmetric-energy collider. We measure decay-time distributions to determine -violating parameters and . We determine these parameters for two ranges of invariant mass: , which is dominated by decays, and a complementary region . Our results have improved precision as compared to previous measurements and are consistent with theory predictions. Published by the American Physical Society2025more » « less
-
pairs may be produced in photonuclear collisions, either from the decays of photoproduced mesons or directly as nonresonant pairs. Measurements of photoproduction probe the couplings between the 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 pairs on lead ions in ultraperipheral collisions using the ALICE detector, including the first investigation of direct production. There is significant production at low transverse momentum, consistent with coherent photoproduction on lead targets. In the mass range above the resonance, for rapidity and , the measured coherent photoproduction cross section is . The center-of-mass energy per nucleon of the photon-nucleus (Pb) system ranges from 33 to 188 GeV, far higher than previous measurements on heavy-nucleus targets. The cross section is larger than expected for photoproduction alone. The mass spectrum is fit to a cocktail consisting of decays, direct photoproduction, and interference between the two. The confidence regions for the amplitude and relative phase angle for direct photoproduction are presented. © 2024 CERN, for the ALICE Collaboration2024CERNmore » « less
An official website of the United States government

