Search

This work proposes an efficient parallel algorithm for non-monotone submodular maximization under a knapsack constraint problem over the ground set of size $n$. Our algorithm improves the best approximation factor of the existing parallel one from $8+\epsilon$ to $7+\epsilon$ with $O(\log n)$ adaptive complexity. The key idea of our approach is to create a new alternate threshold algorithmic framework. This strategy alternately constructs two disjoint candidate solutions within a constant number of sequence rounds. Then, the algorithm boosts solution quality without sacrificing the adaptive complexity. Extensive experimental studies on three applications, Revenue Maximization, Image Summarization, and Maximum Weighted Cut, show that our algorithm not only significantly increases solution quality but also requires comparative adaptivity to state-of-the-art algorithms., Comment: In Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence (IJCAI), Main Track

The problem of non-monotone $k$-submodular maximization under a knapsack constraint ($\kSMK$) over the ground set size $n$ has been raised in many applications in machine learning, such as data summarization, information propagation, etc. However, existing algorithms for the problem are facing questioning of how to overcome the non-monotone case and how to fast return a good solution in case of the big size of data. This paper introduces two deterministic approximation algorithms for the problem that competitively improve the query complexity of existing algorithms. Our first algorithm, $\LAA$, returns an approximation ratio of $1/19$ within $O(nk)$ query complexity. The second one, $\RLA$, improves the approximation ratio to $1/5-\epsilon$ in $O(nk)$ queries, where $\epsilon$ is an input parameter. Our algorithms are the first ones that provide constant approximation ratios within only $O(nk)$ query complexity for the non-monotone objective. They, therefore, need fewer the number of queries than state-of-the-the-art ones by a factor of $\Omega(\log n)$. Besides the theoretical analysis, we have evaluated our proposed ones with several experiments in some instances: Influence Maximization and Sensor Placement for the problem. The results confirm that our algorithms ensure theoretical quality as the cutting-edge techniques and significantly reduce the number of queries., Comment: 12 pages

This work, for the first time, introduces two constant factor approximation algorithms with linear query complexity for non-monotone submodular maximization over a ground set of size $n$ subject to a knapsack constraint, $\mathsf{DLA}$ and $\mathsf{RLA}$. $\mathsf{DLA}$ is a deterministic algorithm that provides an approximation factor of $6+\epsilon$ while $\mathsf{RLA}$ is a randomized algorithm with an approximation factor of $4+\epsilon$. Both run in $O(n \log(1/\epsilon)/\epsilon)$ query complexity. The key idea to obtain a constant approximation ratio with linear query lies in: (1) dividing the ground set into two appropriate subsets to find the near-optimal solution over these subsets with linear queries, and (2) combining a threshold greedy with properties of two disjoint sets or a random selection process to improve solution quality. In addition to the theoretical analysis, we have evaluated our proposed solutions with three applications: Revenue Maximization, Image Summarization, and Maximum Weighted Cut, showing that our algorithms not only return comparative results to state-of-the-art algorithms but also require significantly fewer queries.

Flare frequency distributions represent a key approach to addressing one of the largest problems in solar and stellar physics: determining the mechanism that counter-intuitively heats coronae to temperatures that are orders of magnitude hotter than the corresponding photospheres. It is widely accepted that the magnetic field is responsible for the heating, but there are two competing mechanisms that could explain it: nanoflares or Alfv\'en waves. To date, neither can be directly observed. Nanoflares are, by definition, extremely small, but their aggregate energy release could represent a substantial heating mechanism, presuming they are sufficiently abundant. One way to test this presumption is via the flare frequency distribution, which describes how often flares of various energies occur. If the slope of the power law fitting the flare frequency distribution is above a critical threshold, $\alpha=2$ as established in prior literature, then there should be a sufficient abundance of nanoflares to explain coronal heating. We performed $>$600 case studies of solar flares, made possible by an unprecedented number of data analysts via three semesters of an undergraduate physics laboratory course. This allowed us to include two crucial, but nontrivial, analysis methods: pre-flare baseline subtraction and computation of the flare energy, which requires determining flare start and stop times. We aggregated the results of these analyses into a statistical study to determine that $\alpha = 1.63 \pm 0.03$. This is below the critical threshold, suggesting that Alfv\'en waves are an important driver of coronal heating., Comment: 1,002 authors, 14 pages, 4 figures, 3 tables, published by The Astrophysical Journal on 2023-05-09, volume 948, page 71

Circuit quantum electrodynamics (cQED) experiments on superconducting qubit systems typically employ radiation shields coated in photon absorbing materials to achieve high qubit coherence and low microwave resonator losses. In this work, we present preliminary results on the performance of Vantablack as a novel infrared (IR) shielding material for cQED systems. We compare the coherence properties and residual excited state population (or effective qubit temperature) of a single-junction transmon qubit housed in a shield coated with a standard epoxy-based IR absorbing material, i.e. Berkeley Black, to the coherence and effective temperature of the same qubit in a shield coated in Vantablack. Based on a statistical analysis of multiple qubit coherence measurements we find that the performance of the radiation shield coated with Vantablack is comparable in performance to the standard coating. However, we find that in the Vantablack coated shield the qubit has a higher effective temperature. These results indicate that improvements are likely required to optimize the performance of Vantablack as an IR shielding material for superconducting qubit experiments and we discuss possible routes for such improvements. Finally we describe possible future experiments to more precisely quantify the performance of Vantablack to improve the coherences of more complex cQED systems., Comment: 9 pages, 3 figures, 1 table

A universal supervised neural network (NN) relevant to compute the associated criticalities of real experiments studying phase transitions is constructed. The validity of the built NN is examined by applying it to calculate the criticalities of several three-dimensional (3D) models on the cubic lattice, including the classical $O(3)$ model, the 5-state ferromagnetic Potts model, and a dimerized quantum antiferromagnetic Heisenberg model. Particularly, although the considered NN is only trained one time on a one-dimensional (1D) lattice with 120 sites, yet it has successfully determined the related critical points of the studied 3D systems. Moreover, real configurations of states are not used in the testing stage. Instead, the employed configurations for the prediction are constructed on a 1D lattice of 120 sites and are based on the bulk quantities or the microscopic states of the considered models. As a result, our calculations are ultimately efficient in computation and the applications of the built NN is extremely broaden. Considering the fact that the investigated systems vary dramatically from each other, it is amazing that the combination of these two strategies in the training and the testing stages lead to a highly universal supervised neural network for learning phases and criticalities of 3D models. Based on the outcomes presented in this study, it is favorably probable that much simpler but yet elegant machine learning techniques can be constructed for fields of many-body systems other than the critical phenomena., Comment: 11 pages, 18 figures

We study the quantum criticality at finite temperature for three two-dimensional (2D) $JQ_3$ models using the first principle nonperturbative quantum Monte Carlo calculations (QMC). In particular, the associated universal quantities are obtained and their inverse temperature dependence are investigated. The considered models are known to have quantum phase transitions from the N\'eel order to the valence bond solid. In addition, these transitions are shown to be of second order for two of the studied models, with the remaining one being of first order. Interestingly, we find that the outcomes obtained in our investigation are consistent with the mentioned scenarios regarding the nature of the phase transitions of the three investigated models. Moreover, when the temperature dependence of the studied universal quantities is considered, a substantial difference between the two models possessing second order phase transitions and the remaining model is observed. Remarkably, by using the associated data from both the models that may have continuous transitions, good data collapses are obtained for a number of the considered universal quantities. The findings presented here not only provide numerical evidence to support the results established in the literature regarding the nature of the phase transitions of these $JQ_3$ models, but also can be employed as certain promising criterions to distinguish second order phase transitions from first order ones for the exotic criticalities of the $JQ$-type models. Finally, based on a comparison between the results calculated here and the corresponding theoretical predictions, we conclude that a more detailed analytic calculation is required in order to fully catch the numerical outcomes determined in our investigation., Comment: 8 pages, 15 figures

Weyl semimetals for their exotic topological properties have drawn considerable attention in many research fields. When in combination with s-wave superconductors, the supercurrent can be carried by their topological surface channels, forming junctions mimic the behavior of Majorana bound states. Here, we present a transmon-like superconducting quantum intereference device (SQUID) consists of lateral junctions made of Weyl semimetal Td-MoTe2 and superconducting leads niobium nitride (NbN). The SQUID is coupled to a readout cavity made of molybdenum rhenium (MoRe), whose response at high power reveal the existence of the constituting Josephson junctions (JJs). The loop geometry of the circuit allows the resonant frequency of the readout cavity to be tuned by the magnetic flux. We demonstrate a JJ made of MoTe2 and a flux-tunable transmon-like circuit based on Weyl materials. Our study provides a platform to utilize topological materials in SQUID-based quantum circuits for potential applications in quantum information processing.

A two-dimensional (2D) spin-1/2 antiferromagnetic Heisenberg model with a specific kind of quenched disorder is investigated, using the first principles nonperturbative quantum Monte Carlo calculations (QMC). The employed disorder distribution has a tunable parameter $p$ which can be considered as a measure of the corresponding randomness. In particular, when $p=0$ the disordered system becomes the clean one. Through a large scale QMC, the dynamic critical exponents $z$, the ground state energy densities $E_0$, as well as the Wilson ratios $W$ of various $p$ are determined with high precision. Interestingly, we find that the $p$ dependence of $z$ and $W$ are likely to be complementary to each other. For instance, while the $z$ of $0.4 \le p \le 0.9$ match well among themselves and are statistically different from $z=1$ which corresponds to the clean system, the $W$ for $p < 0.7$ are in reasonable good agreement with that of $p=0$. The technical subtlety of calculating these physical quantities for a disordered system is demonstrated as well. The results presented here are not only interesting from a theoretical perspective, but also can serve as benchmarks for future related studies., Comment: 8 pages, 15 figures

We study the phase transitions of three-dimensional (3D) classical O(3) model and the two-dimensional (2D) classical XY model, as well as both the quantum phase transitions of 2D and 3D dimerized spin-1/2 antiferromagnets, using the techniques of supervised neural network (NN). Moreover, unlike the conventional approaches commonly used in the literature, the training sets employed in our investigation are neither the theoretical nor the real configurations of the considered systems. Remarkably, with such an unconventional set up of the training stage in conjunction with semi-experimental finite-size scaling formulas, the associated critical points determined by the NN method agree well with the established results in the literature. The outcomes obtained here imply that certain unconventional training strategies, like the one used in this study, are not only cost-effective in computation, but are also applicable for a wild range of physical systems., Comment: 14 pages and 33 figures; more references are added; the results of 2D classical XY model are included in this revised version

Using the techniques of Neural Networks (NN), we study the three-dimensional (3D) 5-state ferromagnetic Potts model on the cubic lattice as well as the two-dimensional (2D) 3-state antiferromagnetic Potts model on the square lattice. Unlike the conventional approach, here we follow the idea employed in Ann.~Phy.~391 (2018) 312-331. Specifically, instead of numerically generating numerous objects for the training, the whole or part of the theoretical ground state configurations of the studied models are considered as the training sets. Remarkably, our investigation of these two models provides convincing evidence for the effectiveness of the method of preparing training sets used in this study. In particular, the results of the 3D model obtained here imply that the NN approach is as efficient as the traditional method since the signal of a first order phase transition, namely tunneling between two channels, determined by the NN method is as strong as that calculated with the Monte Carlo technique. Furthermore, the outcomes associated with the considered 2D system indicate even little partial information of the ground states can lead to conclusive results regarding the studied phase transition. The achievements reached in our investigation demonstrate that the performance of NN, using certain amount of the theoretical ground state configurations as the training sets, is impressive., Comment: 9 pages, 14 figures

Inspired by the recent results regarding whether the Harris criterion is valid for quantum spin systems, we have simulated a two-dimensional spin-1/2 Heisenberg model on the square lattice with a specific kind of quenched disorder using the quantum Monte Carlo (QMC) calculations. In particular, the considered quenched disorder has a tunable parameter $0\le p \le 1$ which can be considered as a measure of randomness. Interestingly, when the magnitude of $p$ increases from 0 to 0.9, at the associated quantum phase transitions the numerical value of the correlation length exponent $\nu$ grows from a number compatible with the $O(3)$ result 0.7112(5) to a number slightly greater than 1. In other words, by varying $p$, $\nu$ can reach an outcome between 0.7112(5) and 1 (or greater). Furthermore, among the studied values of $p$, all the associated $\nu$ violate the Harris criterion except the one corresponding to $p=0.9$. Considering the form of the employed disorder here, the above described scenario should remain true for other randomness if it is based on the similar idea as the one used in this study. This is indeed confirmed by our preliminary results stemming from investigating another disorder distribution., Comment: 8 pages, 8 figures, 7 tables

Superfluid helium's low-loss dielectric properties, excellent thermal conductivity, and unique collective excitations make it an attractive candidate to incorporate into superconducting qubit systems. We controllably immerse a three-dimensional superconducting transmon qubit in superfluid helium-4 and measure the spectroscopic and coherence properties of the system. We find that the cavity, the qubit, and their coupling are all modified by the superfluid, which we analyze within the framework of circuit quantum electrodynamics (cQED). At at temperatures relevant to quantum computing experiments, the energy relaxation time of the qubit is not significantly changed by the presence of the superfluid, while the pure dephasing time modestly increases, which we attribute to improved thermalization of the microwave environment via the superfluid., Comment: 11 pages, 8 figures

We demonstrate how the dissipative interaction between a superconducting qubit and a microwave photonic crystal can be used for quantum bath engineering. The photonic crystal is created with a step-impedance transmission line which suppresses and enhances the quantum spectral density of states, influencing decay transitions of a transmon circuit. The qubit interacts with the transmission line indirectly via dispersive coupling to a cavity. We characterize the photonic crystal density of states from both the unitary and dissipative dynamics of the qubit. When the qubit is driven, it dissipates into the frequency dependent density of states of the photonic crystal. Our result is the deterministic preparation of qubit superposition states as the steady-state of coherent driving and dissipation near by the photonic crystal band edge, which we characterize with quantum state tomography. Our results highlight how the multimode environment from the photonic crystal forms a resource for quantum control., Comment: 9 pages 7 figures

In both thermodynamics and quantum mechanics the arrow of time is characterized by the statistical likelihood of physical processes. We characterize this arrow of time for the continuous quantum measurement dynamics of a superconducting qubit. By experimentally tracking individual weak measurement trajectories, we compare the path probabilities of forward and backward-in-time evolution to develop an arrow of time statistic associated with measurement dynamics. We compare the statistics of individual trajectories to ensemble properties showing that the measurement dynamics obeys both detailed and integral fluctuation theorems thus establishing the consistency between microscopic and macroscopic measurement dynamics., Comment: 10 pages 5 figures

The quantum critical regime (QCR) of a two-dimensional (2D) disordered and a 2D clean dimerized spin-$\frac{1}{2}$ Heisenberg models are studied using the first principles nonperturbative quantum Monte Carlo simulations (QMC). In particular, the three well-known universal coefficients associated with QCR are investigated in detail. While in our investigation we find the obtained results are consistent with the related analytic predictions, non-negligible finite temperature ($T$) effects are observed. Such an influence from $T$ on the properties of the considered spin systems related to QCR has not been explored thoroughly before. Moreover, the most striking finding in our study is that the numerical value for one of the universal coefficients we determine is likely to be different significantly from the corresponding result(s) established in the literature. To better understand the sources for the discrepancy observed here, apart from carrying out the associated analytic calculations not considered previously, it will be desirable as well to conduct a comprehensive examination of the exotic features of QCR for other disordered and clean spin systems than those investigated in this study., Comment: 10 pages, 22 figures, several paragraphs are modified to reflect the current status of the related calculations

Inspired by the recently theoretical development relevant to the experimental data of TlCuCl$_3$, particularly those associated with the universal scaling between the N\'eel temperature $T_N$ and the staggered magnetization density $M_s$, we carry a detailed investigation of 3-dimensional (3D) dimerized quantum antiferromagnets using the first principles quantum Monte Carlo calculations. The motivation behind our study is to better understand the microscopic effects on these scaling relations of $T_N$ and $M_s$, hence to shed some light on some of the observed inconsistency between the theoretical and the experimental results. Remarkably, for the considered 3D dimerized models, we find that the established universal scaling relations can indeed be categorized by the amount of stronger antiferromagnetic couplings connected to a lattice site. Convincing numerical evidence is provided to support this conjecture. The relevance of the outcomes presented here to the experiments of TlCuCl$_3$ is briefly discussed as well., Comment: 9 pages, 27 figures

We use homodyne detection to monitor the radiative decay of a superconducting qubit. According to the classical theory of conditional probabilities, the excited state population differs from an exponential decay law if it is conditioned upon a later projective qubit measurement. Quantum trajectory theory accounts for the expectation values of general observables, and we use experimental data to show how a homodyne detection signal is conditioned upon both the initial state and the finally projected state of a decaying qubit. We observe, in particular, how anomalous weak values occur in continuous weak measurement for certain pre- and post-selected states. Subject to homodyne detection, the density matrix evolves in a stochastic manner, but it is restricted to a specific surface in the Bloch sphere. We show that a similar restriction applies to the information associated with the post-selection, and thus bounds the predictions of the theory., Comment: 11 pages, 8 figures

We use a near quantum limited detector to experimentally track individual quantum state trajectories of a driven qubit formed by the hybridization of a waveguide cavity and a transmon circuit. For each measured quantum coherent trajectory, we separately identify energy changes of the qubit as heat and work, and verify the first law of thermodynamics for an open quantum system. We further establish the consistency of these results by comparison with the master equation approach and the two-projective-measurement scheme, both for open and closed dynamics, with the help of a quantum feedback loop that compensates for the exchanged heat and effectively isolates the qubit., Comment: 11 pages, 7 figures

We employ phase-sensitive amplification to perform homodyne detection of the resonance fluorescence from a driven superconducting artificial atom. Entanglement between the emitter and its fluorescence allows us to track the individual quantum state trajectories of the emitter conditioned on the outcomes of the field measurements. We analyze the ensemble properties of these trajectories by considering trajectories that connect specific initial and final states. By applying the stochastic path integral formalism, we calculate equations-of-motion for the most likely path between two quantum states and compare these predicted paths to experimental data. Drawing on the mathematical similarity between the action formalism of the most likely quantum paths and ray optics we study the emergence of caustics in quantum trajectories---places where multiple extrema in the stochastic action occur. We observe such multiple most likely paths in experimental data and find these paths to be in reasonable quantitative agreement with theoretical calculations., Comment: 12 pages, 10 figures