Search

Recent years have witnessed the remarkable success of applying Graph machine learning (GML) to node/graph classification and link prediction. However, edge classification task that enjoys numerous real-world applications such as social network analysis and cybersecurity, has not seen significant advancement. To address this gap, our study pioneers a comprehensive approach to edge classification. We identify a novel `Topological Imbalance Issue', which arises from the skewed distribution of edges across different classes, affecting the local subgraph of each edge and harming the performance of edge classifications. Inspired by the recent studies in node classification that the performance discrepancy exists with varying local structural patterns, we aim to investigate if the performance discrepancy in topological imbalanced edge classification can also be mitigated by characterizing the local class distribution variance. To overcome this challenge, we introduce Topological Entropy (TE), a novel topological-based metric that measures the topological imbalance for each edge. Our empirical studies confirm that TE effectively measures local class distribution variance, and indicate that prioritizing edges with high TE values can help address the issue of topological imbalance. Based on this, we develop two strategies - Topological Reweighting and TE Wedge-based Mixup - to focus training on (synthetic) edges based on their TEs. While topological reweighting directly manipulates training edge weights according to TE, our wedge-based mixup interpolates synthetic edges between high TE wedges. Ultimately, we integrate these strategies into a novel topological imbalance strategy for edge classification: TopoEdge. Through extensive experiments, we demonstrate the efficacy of our proposed strategies on newly curated datasets and thus establish a new benchmark for (imbalanced) edge classification.

Random reversible and quantum circuits form random walks on the alternating group $\mathrm{Alt}(2^n)$ and unitary group $\mathrm{SU}(2^n)$, respectively. Known bounds on the spectral gap for the $t$-th moment of these random walks have inverse-polynomial dependence in both $n$ and $t$. We prove that the gap for random reversible circuits is $\Omega(n^{-3})$ for all $t\geq 1$, and the gap for random quantum circuits is $\Omega(n^{-3})$ for $t \leq \Theta(2^{n/2})$. These gaps are independent of $t$ in the respective regimes. We can further improve both gaps to $n^{-1}/\mathrm{polylog}(n, t)$ for $t\leq 2^{\Theta(n)}$, which is tight up to polylog factors. Our spectral gap results have a number of consequences: 1) Random reversible circuits with $\mathcal{O}(n^4 t)$ gates form multiplicative-error $t$-wise independent (even) permutations for all $t\geq 1$; for $t \leq \Theta(2^{n/6.1})$, we show that $\tilde{\mathcal{O}}(n^2 t)$ gates suffice. 2) Random quantum circuits with $\mathcal{O}(n^4 t)$ gates form multiplicative-error unitary $t$-designs for $t \leq \Theta(2^{n/2})$; for $t\leq \Theta(2^{2n/5})$, we show that $\tilde{\mathcal{O}}(n^2t)$ gates suffice. 3) The robust quantum circuit complexity of random circuits grows linearly for an exponentially long time, proving the robust Brown--Susskind conjecture [BS18,BCHJ+21]. Our spectral gap bounds are proven by reducing random quantum circuits to a more structured walk: a modification of the ``$\mathrm{PFC}$ ensemble'' from [MPSY24] together with an expander on the alternating group due to Kassabov [Kas07a], for which we give an efficient implementation using reversible circuits. In our reduction, we approximate the structured walk with local random circuits without losing the gap, which uses tools from the study of frustration-free Hamiltonians., Comment: 80 pages, 5 figures, v2: added references and minor changes in the presentation

Mid-circuit measurement (MCM) is a crucial ingredient in the development of fault-tolerant quantum computation. While there have been rapid experimental progresses in realizing MCM, a systematic method for characterizing noisy MCM is still under exploration. In this work we develop an algorithm to characterize noisy MCM, via a generalization of cycle benchmarking -- a standard approach for characterizing the Pauli noise channel of Clifford gates. The key idea is to use a joint Fourier transform on the classical and quantum registers and then estimate parameters in the Fourier space, analogous to Pauli fidelities used in cycle benchmarking. Furthermore, we develop a theory of the noise learnability of MCM, which determines what information can be learned about the noise model (in the presence of state preparation and measurement noise) and what cannot, which shows that all learnable information can be learned using our algorithm. As an application, we show how to use the learned information to test the independence between measurement noise and state preparation noise in a MCM. Finally, we conduct numerical simulations to illustrate the practical applicability of the algorithm. Similar to cycle benchmarking, we expect the algorithm to provide a useful toolkit that is of experimental interest., Comment: 27 pages, 9 figures

A quantum system coupled to a bath at some fixed, finite temperature converges to its Gibbs state. This thermalization process defines a natural, physically-motivated model of quantum computation. However, whether quantum computational advantage can be achieved within this realistic physical setup has remained open, due to the challenge of finding systems that thermalize quickly, but are classically intractable. Here we consider sampling from the measurement outcome distribution of quantum Gibbs states at constant temperatures, and prove that this task demonstrates quantum computational advantage. We design a family of commuting local Hamiltonians (parent Hamiltonians of shallow quantum circuits) and prove that they rapidly converge to their Gibbs states under the standard physical model of thermalization (as a continuous-time quantum Markov chain). On the other hand, we show that no polynomial time classical algorithm can sample from the measurement outcome distribution by reducing to the classical hardness of sampling from noiseless shallow quantum circuits. The key step in the reduction is constructing a fault-tolerance scheme for shallow IQP circuits against input noise., Comment: To appear in FOCS 2024. v2: Improved main result to constant locality

We construct random walks on simple Lie groups that quickly converge to the Haar measure for all moments up to order $t$. Specifically, a step of the walk on the unitary or orthognoal group of dimension $2^{\mathsf n}$ is a random Pauli rotation $e^{\mathrm i \theta P /2}$. The spectral gap of this random walk is shown to be $\Omega(1/t)$, which coincides with the best previously known bound for a random walk on the permutation group on $\{0,1\}^{\mathsf n}$. This implies that the walk gives an $\varepsilon$-approximate unitary $t$-design in depth $O(\mathsf n t^2 + t \log 1/\varepsilon)d$ where $d=O(\log \mathsf n)$ is the circuit depth to implement $e^{\mathrm i \theta P /2}$. Our simple proof uses quadratic Casimir operators of Lie algebras., Comment: 21 pages, 1 figure

Despite fundamental interests in learning quantum circuits, the existence of a computationally efficient algorithm for learning shallow quantum circuits remains an open question. Because shallow quantum circuits can generate distributions that are classically hard to sample from, existing learning algorithms do not apply. In this work, we present a polynomial-time classical algorithm for learning the description of any unknown $n$-qubit shallow quantum circuit $U$ (with arbitrary unknown architecture) within a small diamond distance using single-qubit measurement data on the output states of $U$. We also provide a polynomial-time classical algorithm for learning the description of any unknown $n$-qubit state $\lvert \psi \rangle = U \lvert 0^n \rangle$ prepared by a shallow quantum circuit $U$ (on a 2D lattice) within a small trace distance using single-qubit measurements on copies of $\lvert \psi \rangle$. Our approach uses a quantum circuit representation based on local inversions and a technique to combine these inversions. This circuit representation yields an optimization landscape that can be efficiently navigated and enables efficient learning of quantum circuits that are classically hard to simulate., Comment: 10 pages, 14 figures (7 inline; 7 floating) + 76-page appendix

Graph Neural Networks (GNNs) have shown great promise in learning node embeddings for link prediction (LP). While numerous studies aim to improve the overall LP performance of GNNs, none have explored its varying performance across different nodes and its underlying reasons. To this end, we aim to demystify which nodes will perform better from the perspective of their local topology. Despite the widespread belief that low-degree nodes exhibit poorer LP performance, our empirical findings provide nuances to this viewpoint and prompt us to propose a better metric, Topological Concentration (TC), based on the intersection of the local subgraph of each node with the ones of its neighbors. We empirically demonstrate that TC has a higher correlation with LP performance than other node-level topological metrics like degree and subgraph density, offering a better way to identify low-performing nodes than using cold-start. With TC, we discover a novel topological distribution shift issue in which newly joined neighbors of a node tend to become less interactive with that node's existing neighbors, compromising the generalizability of node embeddings for LP at testing time. To make the computation of TC scalable, We further propose Approximated Topological Concentration (ATC) and theoretically/empirically justify its efficacy in approximating TC and reducing the computation complexity. Given the positive correlation between node TC and its LP performance, we explore the potential of boosting LP performance via enhancing TC by re-weighting edges in the message-passing and discuss its effectiveness with limitations. Our code is publicly available at https://github.com/YuWVandy/Topo_LP_GNN.

Recommender systems are effective tools for mitigating information overload and have seen extensive applications across various domains. However, the single focus on utility goals proves to be inadequate in addressing real-world concerns, leading to increasing attention to fairness-aware and diversity-aware recommender systems. While most existing studies explore fairness and diversity independently, we identify strong connections between these two domains. In this survey, we first discuss each of them individually and then dive into their connections. Additionally, motivated by the concepts of user-level and item-level fairness, we broaden the understanding of diversity to encompass not only the item level but also the user level. With this expanded perspective on user and item-level diversity, we re-interpret fairness studies from the viewpoint of diversity. This fresh perspective enhances our understanding of fairness-related work and paves the way for potential future research directions. Papers discussed in this survey along with public code links are available at https://github.com/YuyingZhao/Awesome-Fairness-and-Diversity-Papers-in-Recommender-Systems .

We give a polynomial time classical algorithm for sampling from the output distribution of a noisy random quantum circuit in the regime of anti-concentration to within inverse polynomial total variation distance. This gives strong evidence that, in the presence of a constant rate of noise per gate, random circuit sampling (RCS) cannot be the basis of a scalable experimental violation of the extended Church-Turing thesis. Our algorithm is not practical in its current form, and does not address finite-size RCS based quantum supremacy experiments., Comment: 27 pages, 2 figures

Recently, several quantum benchmarking algorithms have been developed to characterize noisy quantum gates on today's quantum devices. A well-known issue in benchmarking is that not everything about quantum noise is learnable due to the existence of gauge freedom, leaving open the question of what information about noise is learnable and what is not, which has been unclear even for a single CNOT gate. Here we give a precise characterization of the learnability of Pauli noise channels attached to Clifford gates, showing that learnable information corresponds to the cycle space of the pattern transfer graph of the gate set, while unlearnable information corresponds to the cut space. This implies the optimality of cycle benchmarking, in the sense that it can learn all learnable information about Pauli noise. We experimentally demonstrate noise characterization of IBM's CNOT gate up to 2 unlearnable degrees of freedom, for which we obtain bounds using physical constraints. In addition, we give an attempt to characterize the unlearnable information by assuming perfect initial state preparation. However, based on the experimental data, we conclude that this assumption is inaccurate as it yields unphysical estimates, and we obtain a lower bound on state preparation noise., Comment: 33 pages, 11 figures. Close to accepted version

As small quantum computers are becoming available on different physical platforms, a benchmarking task known as cross-platform verification has been proposed that aims to estimate the fidelity of states prepared on two quantum computers. This task is fundamentally distributed, as no quantum communication can be performed between the two physical platforms due to hardware constraints, which prohibits a joint SWAP test. In this paper we settle the sample complexity of this task across all measurement and communication settings. The essence of the task, which we call distributed quantum inner product estimation, involves two players Alice and Bob who have $k$ copies of unknown states $\rho,\sigma$ (acting on $\mathbb{C}^{d}$) respectively. Their goal is to estimate $\mathrm{Tr}(\rho\sigma)$ up to additive error $\varepsilon\in(0,1)$, using local quantum operations and classical communication. In the weakest setting where only non-adaptive single-copy measurements and simultaneous message passing are allowed, we show that $k=O(\max\{1/\varepsilon^2,\sqrt{d}/\varepsilon\})$ copies suffice. This achieves a savings compared to full tomography which takes $\Omega(d^3)$ copies with single-copy measurements. Surprisingly, we also show that the sample complexity must be at least $\Omega(\max\{1/\varepsilon^2,\sqrt{d}/\varepsilon\})$, even in the strongest setting where adaptive multi-copy measurements and arbitrary rounds of communication are allowed. This shows that the success achieved by shadow tomography, for sample-efficiently learning the properties of a single system, cannot be generalized to the distributed setting. Furthermore, the fact that the sample complexity remains the same with single and multi-copy measurements contrasts with single system quantum property testing, which often demonstrate exponential separations in sample complexity with single and multi-copy measurements., Comment: 47 pages, 3 figures

The increasing scale of near-term quantum hardware motivates the need for efficient noise characterization methods, since qubit and gate level techniques cannot capture crosstalk and correlated noise in many qubit systems. While scalable approaches, such as cycle benchmarking, are known for special classes of quantum circuits, the characterization of noise in general circuits with non-Clifford gates has been an unreachable task. We develop an algorithm that can sample-efficiently estimate the total amount of noise induced by a layer of arbitrary non-Clifford gates, including all crosstalks, and experimentally demonstrate the method on IBM Quantum hardware. Our algorithm is inspired by Google's quantum supremacy experiment and is based on random circuit sampling. In their paper, Google observed that their experimental linear cross entropy was consistent with a simple uncorrelated noise model, and claimed this coincidence indicated that the noise in their device was uncorrelated -- a key step in hardware development towards fault tolerance. As an application, we show that our result provides formal evidence to support such a conclusion., Comment: 43 pages, 15 figures; presentation updated, results unchanged

Noise is the defining feature of the NISQ era, but it remains unclear if noisy quantum devices are capable of quantum speedups. Quantum supremacy experiments have been a major step forward, but gaps remain between the theory behind these experiments and their actual implementations. In this work we initiate the study of the complexity of quantum random circuit sampling experiments with realistic amounts of noise. Actual quantum supremacy experiments have high levels of uncorrected noise and exponentially decaying fidelities. It is natural to ask if there is any signal of exponential complexity in these highly noisy devices. Surprisingly, we show that it remains hard to compute the output probabilities of noisy random quantum circuits without error correction. More formally, so long as the noise rate of the device is below the error detection threshold, we show it is #P-hard to compute the output probabilities of random circuits with a constant rate of noise per gate. This hardness persists even though these probabilities are exponentially close to uniform. Interestingly these hardness results also have implications for the complexity of experiments in a low-noise setting. The issue here is that prior hardness results for computing output probabilities of random circuits are not robust enough to imprecision to connect with the Stockmeyer argument for hardness of sampling from circuits with constant fidelity. We exponentially improve the robustness of prior results to imprecision, both in the cases of Random Circuit Sampling and BosonSampling. In the latter case we bring the proven hardness within a constant factor in the exponent of the robustness required for hardness of sampling for the first time. We then show that our results are in tension with one another -- the high-noise result implies the low-noise result is essentially optimal, even with generalizations of our techniques., Comment: 43 pages, 2 figures, presented at QIP 2021

Over the past few years several quantum machine learning algorithms were proposed that promise quantum speed-ups over their classical counterparts. Most of these learning algorithms either assume quantum access to data -- making it unclear if quantum speed-ups still exist without making these strong assumptions, or are heuristic in nature with no provable advantage over classical algorithms. In this paper, we establish a rigorous quantum speed-up for supervised classification using a general-purpose quantum learning algorithm that only requires classical access to data. Our quantum classifier is a conventional support vector machine that uses a fault-tolerant quantum computer to estimate a kernel function. Data samples are mapped to a quantum feature space and the kernel entries can be estimated as the transition amplitude of a quantum circuit. We construct a family of datasets and show that no classical learner can classify the data inverse-polynomially better than random guessing, assuming the widely-believed hardness of the discrete logarithm problem. Meanwhile, the quantum classifier achieves high accuracy and is robust against additive errors in the kernel entries that arise from finite sampling statistics., Comment: 27 pages, 2 figures

Quantum error correction is an essential ingredient for universal quantum computing. Despite tremendous experimental efforts in the study of quantum error correction, to date, there has been no demonstration in the realisation of universal quantum error correcting code, with the subsequent verification of all key features including the identification of an arbitrary physical error, the capability for transversal manipulation of the logical state, and state decoding. To address this challenge, we experimentally realise the $[\![5,1,3]\!]$ code, the so-called smallest perfect code that permits corrections of generic single-qubit errors. In the experiment, having optimised the encoding circuit, we employ an array of superconducting qubits to realise the $[\![5,1,3]\!]$ code for several typical logical states including the magic state, an indispensable resource for realising non-Clifford gates. The encoded states are prepared with an average fidelity of $57.1(3)\%$ while with a high fidelity of $98.6(1)\%$ in the code space. Then, the arbitrary single-qubit errors introduced manually are identified by measuring the stabilizers. We further implement logical Pauli operations with a fidelity of $97.2(2)\%$ within the code space. Finally, we realise the decoding circuit and recover the input state with an overall fidelity of $74.5(6)\%$, in total with $92$ gates. Our work demonstrates each key aspect of the $[\![5,1,3]\!]$ code and verifies the viability of experimental realization of quantum error correcting codes with superconducting qubits., Comment: 6 pages, 4 figures + Supplementary Materials

Quantum memory -- the capacity to store and faithfully recover unknown quantum states -- is essential for quantum-enhanced technology. There is thus a pressing need for operationally meaningful means to benchmark candidate memories across diverse physical platforms. Here we introduce a universal benchmark distinguished by its relevance across multiple key operational settings, exactly quantifying (1) the memory's robustness to noise, (2) the number of noiseless qubits needed for its synthesis, (3) its potential to speed up statistical sampling tasks, and (4) performance advantage in non-local games beyond classical limits. The measure is analytically computable for low-dimensional systems and can be efficiently bounded in experiment without tomography. We thus illustrate quantum memory as a meaningful resource, with our benchmark reflecting both its cost of creation and what it can accomplish. We demonstrate the benchmark on the five-qubit IBM Q hardware, and apply it to witness efficacy of error-suppression techniques and quantify non-Markovian noise. We thus present an experimentally accessible, practically meaningful, and universally relevant quantifier of a memory's capability to preserve quantum advantage., Comment: 30 pages

Quantum resource theories have been widely studied to systematically characterize the non-classicality of quantum systems. Most resource theories focus on quantum states and study their interconversions. Although quantum channels are generally used as the tool for state manipulation, such a manipulation capability can be naturally regarded as a generalized quantum resource, leading to an open research direction in the resource theories of quantum channels. Various resource-theoretic properties of channels have been investigated, however, without treating channels themselves as operational resources that can also be manipulated and converted. In this Letter, we address this problem by first proposing a general resource framework for quantum channels and introducing resource monotones based on general distance quantifiers of channels. We study the interplay between channel and state resource theories by relating resource monotones of a quantum channel to its manipulation power of the state resource. Regarding channels as operational resources, we introduce asymptotic channel distillation and dilution, the most important tasks in an operational resource theory, and show how to bound the conversion rates with channel resource monotones. Finally, we apply our results to quantum coherence as an example and introduce the coherence of channels, which characterizes the coherence generation ability of channels. We consider asymptotic channel distillation and dilution with maximally incoherent operations and find the theory asymptotically irreversible, in contrast to the asymptotic reversibility of the coherence of states., Comment: 17 pages, 2 figures

Device-independent (DI) tests allow to witness and quantify the quantum feature of a system, such as entanglement, without trusting the implementation devices. Although DI test is a powerful tool in many quantum information tasks, it generally requires nonlocal settings. Fundamentally, the superposition property of quantum states, quantified by coherence measures, is a distinct feature to distinguish quantum mechanics from classical theories. In literature, witness and quantification of coherence with trusted devices have been well-studied. However, it remains open whether we can witness and quantify single party coherence with untrusted devices, as it is not clear whether the concept of DI tests exists without a nonlocal setting. In this work, we study DI witness and quantification of coherence with untrusted devices. First, we prove a no-go theorem for a fully DI scenario, as well as a semi DI scenario employing a joint measurement with trusted ancillary states. We then propose a general prepare-and-measure semi DI scheme for witnessing and quantifying the amount of coherence. We show how to quantify the relative entropy and the $l_1$ norm of single party coherence with analytical and numerical methods. As coherence is a fundamental resource for tasks such as quantum random number generation and quantum key distribution, we expect our result may shed light on designing new semi DI quantum cryptographic schemes., Comment: 14 pages, 7 figures, comments are welcome!

The resource framework of quantum coherence was introduced by Baumgratz, Cramer and Plenio [PRL 113, 140401 (2014)] and further developed by Winter and Yang [PRL 116, 120404 (2016)]. We consider the one-shot problem of distilling pure coherence from a single instance of a given resource state. Specifically, we determine the distillable coherence with a given fidelity under incoherent operations (IO) through a generalisation of the Winter-Yang protocol. This is compared to the distillable coherence under maximal incoherent operations (MIO) and dephasing-covariant incoherent operations (DIO), which can be cast as a semidefinite programme, that has been presented previously by Regula et al. [PRL 121, 010401 (2018)]. Our results are given in terms of a smoothed min-relative entropy distance from the incoherent set of states, and a variant of the hypothesis-testing relative entropy distance, respectively. The one-shot distillable coherence is also related to one-shot randomness extraction. Moreover, from the one-shot formulas under IO, MIO, DIO, we can recover the optimal distillable rate in the many-copy asymptotics, yielding the relative entropy of coherence. These results can be compared with previous work by some of the present authors [Zhao et al., PRL 120, 070403 (2018)] on one-shot coherence formation under IO, MIO, DIO and also SIO. This shows that the amount of distillable coherence is essentially the same for IO, DIO, and MIO, despite the fact that the three classes of operations are very different. We also relate the distillable coherence under strictly incoherent operations (SIO) to a constrained hypothesis testing problem and explicitly show the existence of bound coherence under SIO in the asymptotic regime., Comment: 13 pages, 1 figure, IEEE style IEEEtran.cls

Quantum coherence characterizes the non-classical feature of a single party system with respect to a local basis. Based on a recently introduced resource framework, coherence can be regarded as a resource and be systematically manipulated and quantified. Operationally, considering the projective measurement of the state in the computational basis, coherence quantifies the intrinsic randomness of the measurement outcome conditioned on all the other quantum systems. However, such a relation is only proven when randomness is characterized by the Von-Neumann entropy. In this work, we consider several recently proposed coherence measures and relate them to the general uncertainties of the projective measurement outcome conditioned on all the other systems. Our work thus provides a unified framework for redefining several coherence measures via general conditional entropies. Based on the relation, we numerically calculate the coherence measures via semi-definite programming. Furthermore, we discuss the operational meaning of the unified definition. Our result highlights the close relation between single partite coherence and bipartite quantum correlation., Comment: 19 pages, 2 figures, comments are very welcome!

Manipulation and quantification of quantum resources are fundamental problems in quantum physics. In the asymptotic limit, coherence distillation and dilution have been proposed by manipulating infinite identical copies of states. In the non-asymptotic setting, finite data-size effects emerge, and the practically relevant problem of coherence manipulation using finite resources has been left open. This letter establishes the one-shot theory of coherence dilution, which involves converting maximally coherent states into an arbitrary quantum state using maximally incoherent operations, dephasing-covariant incoherent operations, incoherent operations, or strictly incoherent operations. We introduce several coherence monotones with concrete operational interpretations that estimate the one-shot coherence cost --- the minimum amount of maximally coherent states needed for faithful coherence dilution. Furthermore, we derive the asymptotic coherence dilution results with maximally incoherent operations, incoherent operations, and strictly incoherent operations as special cases. Our result can be applied in the analyses of quantum information processing tasks that exploit coherence as resources, such as quantum key distribution and random number generation., Comment: 12 pages, 1 figure, comments are welcome!