Search

Fluxonium qubits are recognized for their high coherence times and high operation fidelities, attributed to their unique design incorporating over 100 Josephson junctions per superconducting loop. However, this complexity poses significant fabrication challenges, particularly in achieving high yield and junction uniformity with traditional methods. Here, we introduce an overlap process for Josephson junction fabrication that achieves nearly 100% yield and maintains uniformity across a 2-inch wafer with less than 5% variation for the phase slip junction and less than 2% for the junction array. Our compact junction array design facilitates fluxonium qubits with energy relaxation times exceeding 1 millisecond at the flux frustration point, demonstrating consistency with state-of-the-art dielectric loss tangents and flux noise across multiple devices. This work suggests the scalability of high coherence fluxonium processors using CMOS-compatible processes, marking a significant step towards practical quantum computing.

Introducing disorderness in the superconducting materials has been considered promising to enhance the electromagnetic impedance and realize noise-resilient superconducting qubits. Despite a number of pioneering implementations, the understanding of the correlation between the material disorderness and the qubit coherence is still developing. Here, we demonstrate the first and a systematic characterization of fluxonium qubits with the superinductors made from titanium-aluminum-nitride with varied disorderness. From qubit noise spectroscopy, the flux noise and the dielectric loss are extracted as a measure of the coherence properties. Our results reveal that the $1/f$ flux noise dominates the qubit decoherence around the flux-frustration point, strongly correlated with the material disorderness; while the dielectric loss remains low under a wide range of material properties. From the flux-noise amplitudes, the areal density ($\sigma$) of the phenomenological spin defects and material disorderness are found to be approximately correlated by $\sigma \propto \rho_{xx}^3$, or effectively $(k_F l)^{-3}$. This work has provided new insights on the origin of decoherence channels within superconductors, and could serve as a useful guideline for material design and optimization.

The fluxonium qubits have emerged as a promising platform for gate-based quantum information processing. However, their extraordinary protection against charge fluctuations comes at a cost: when coupled capacitively, the qubit-qubit interactions are restricted to XX-interactions. Consequently, effective XX- or XZ-interactions are only constructed either by temporarily populating higher-energy states, or by exploiting perturbative effects under microwave driving. Instead, we propose and demonstrate an inductive coupling scheme, which offers a wide selection of native qubit-qubit interactions for fluxonium. In particular, we leverage a built-in, flux-controlled ZZ-interaction to perform qubit entanglement. To combat the increased flux-noise-induced dephasing away from the flux-insensitive position, we use a continuous version of the dynamical decoupling scheme to perform noise filtering. Combining these, we demonstrate a 20 ns controlled-Z (CZ) gate with a mean fidelity of 99.53%. More than confirming the efficacy of our gate scheme, this high-fidelity result also reveals a promising but rarely explored parameter space uniquely suitable for gate operations between fluxonium qubits.

Scaling bottlenecks the making of digital quantum computers, posing challenges from both the quantum and the classical components. We present a classical architecture to cope with a comprehensive list of the latter challenges {\em all at once}, and implement it fully in an end-to-end system by integrating a multi-core RISC-V CPU with our in-house control electronics. Our architecture enables scalable, high-precision control of large quantum processors and accommodates evolving requirements of quantum hardware. A central feature is a microarchitecture executing quantum operations in parallel on arbitrary predefined qubit groups. Another key feature is a reconfigurable quantum instruction set that supports easy qubit re-grouping and instructions extensions. As a demonstration, we implement the widely-studied surface code quantum computing workflow, which is instructive for being demanding on both the controllers and the integrated classical computation. Our design, for the first time, reduces instruction issuing and transmission costs to constants, which do not scale with the number of qubits, without adding any overheads in decoding or dispatching. Rather than relying on specialized hardware for syndrome decoding, our system uses a dedicated multi-core CPU for both qubit control and classical computation, including syndrome decoding. This simplifies the system design and facilitates load-balancing between the quantum and classical components. We implement recent proposals as decoding firmware on a RISC-V system-on-chip (SoC) that parallelizes general inner decoders. By using our in-house Union-Find and PyMatching 2 implementations, we can achieve unprecedented decoding capabilities of up to distances 47 and 67 with the currently available SoCs, under realistic and optimistic assumptions of physical error rate $p=0.001 and p=0.0001, respectively, all in just 1 \textmu s., Comment: 12 pages, 12 figures

Using a fluxonium qubit with in situ tunability of its Josephson energy, we characterize its energy relaxation at different flux biases as well as different Josephson energy values. The relaxation rate at qubit energy values, ranging more than one order of magnitude around the thermal energy $k_B T$, can be quantitatively explained by a combination of dielectric loss and $1/f$ flux noise with a crossover point. The amplitude of the $1/f$ flux noise is consistent with that extracted from the qubit dephasing measurements at the flux sensitive points. In the dielectric loss dominant regime, the loss is consistent with that arises from the electric dipole interaction with two-level-system (TLS) defects. In particular, as increasing Josephson energy thus decreasing qubit frequency at the flux insensitive spot, we find that the qubit exhibits increasingly weaker coupling to TLS defects thus desirable for high-fidelity quantum operations.

Fast classical processing is essential for most quantum fault-tolerance architectures. We introduce a sliding-window decoding scheme that provides fast classical processing for the surface code through parallelism. Our scheme divides the syndromes in spacetime into overlapping windows along the time direction, which can be decoded in parallel with any inner decoder. With this parallelism, our scheme can solve the decoding throughput problem as the code scales up, even if the inner decoder is slow. When using min-weight perfect matching and union-find as the inner decoders, we observe circuit-level thresholds of $0.68\%$ and $0.55\%$, respectively, which are almost identical to $0.70\%$ and $0.55\%$ for the batch decoding., Comment: Main text: 6 pages, 3 figures. Supplementary material: 18 pages, 14 figures. V2: added data and updated general formalism

Dielectric loss is one of the major decoherence sources of superconducting qubits. Contemporary high-coherence superconducting qubits are formed by material systems mostly consisting of superconducting films on substrate with low dielectric loss, where the loss mainly originates from the surfaces and interfaces. Among the multiple candidates for material systems, a combination of titanium nitride (TiN) film and sapphire substrate has good potential because of its chemical stability against oxidization, and high quality at interfaces. In this work, we report a TiN film deposited onto sapphire substrate achieving low dielectric loss at the material interface. Through the systematic characterizations of a series of transmon qubits fabricated with identical batches of TiN base layers, but different geometries of qubit shunting capacitors with various participation ratios of the material interface, we quantitatively extract the loss tangent value at the substrate-metal interface smaller than $8.9 \times 10^{-4}$ in 1-nm disordered layer. By optimizing the interface participation ratio of the transmon qubit, we reproducibly achieve qubit lifetimes of up to 300 $\mu$s and quality factors approaching 8 million. We demonstrate that TiN film on sapphire substrate is an ideal material system for high-coherence superconducting qubits. Our analyses further suggest that the interface dielectric loss around the Josephson junction part of the circuit could be the dominant limitation of lifetimes for state-of-the-art transmon qubits.

Superconducting qubits provide a promising path toward building large-scale quantum computers. The simple and robust transmon qubit has been the leading platform, achieving multiple milestones. However, fault-tolerant quantum computing calls for qubit operations at error rates significantly lower than those exhibited in the state of the art. Consequently, alternative superconducting qubits with better error protection have attracted increasing interest. Among them, fluxonium is a particularly promising candidate, featuring large anharmonicity and long coherence times. Here, we engineer a fluxonium-based quantum processor that integrates high qubit-coherence, fast frequency-tunability, and individual-qubit addressability for reset, readout, and gates. With simple and fast gate schemes, we achieve an average single-qubit gate fidelity of 99.97% and a two-qubit gate fidelity of up to 99.72%. This performance is comparable to the highest values reported in the literature of superconducting circuits. Thus our work, for the first time within the realm of superconducting qubits, reveals an approach toward fault-tolerant quantum computing that is alternative and competitive to the transmon system.

Disordered superconducting nitrides with kinetic inductance have long been considered a leading material candidate for high-inductance quantum-circuit applications. Despite continuing efforts in reducing material dimensions to increase the kinetic inductance and the corresponding circuit impedance, it becomes a fundamental challenge to improve further without compromising material qualities. To this end, we propose a method to drastically increase the kinetic inductance of superconducting materials via spinodal decomposition while keeping a low microwave loss. We use epitaxial Ti\textsubscript{0.48}Al\textsubscript{0.52}N as a model system, and for the first time demonstrate the utilization of spinodal decomposition to trigger the insulator-to-superconductor transition with a drastically enhanced material disorder. The measured kinetic inductance has increased by 2-3 orders of magnitude compared with all the best reported disordered superconducting nitrides. Our work paves the way for substantially enhancing and deterministically controlling the inductance for advanced superconducting quantum circuits.

A quantum instruction set is where quantum hardware and software meet. We develop new characterization and compilation techniques for non-Clifford gates to accurately evaluate different quantum instruction set designs. We specifically apply them to our fluxonium processor that supports mainstream instruction $\mathrm{iSWAP}$ by calibrating and characterizing its square root $\mathrm{SQiSW}$. We measure a gate fidelity of up to $99.72\%$ with an average of $99.31\%$ and realize Haar random two-qubit gates using $\mathrm{SQiSW}$ with an average fidelity of $96.38\%$. This is an average error reduction of $41\%$ for the former and a $50\%$ reduction for the latter compared to using $\mathrm{iSWAP}$ on the same processor. This shows designing the quantum instruction set consisting of $\mathrm{SQiSW}$ and single-qubit gates on such platforms leads to a performance boost at almost no cost., Comment: 2 figures in main text and 21 figures in Supplementary Materials. This manuscript subsumes version 1 with significant improvements such as experimental demonstration and materials presentation

Superconducting quantum circuits is one of the leading candidates for a universal quantum computer. Designing novel qubit and multiqubit superconducting circuits requires the ability to simulate and analyze the properties of a general circuit. In particular, going outside the transmon approach, we cannot make assumptions on anharmonicity, thus precluding blackbox quantization approaches and necessitating the formal circuit quantization approach. We consider and solve two issues involved in simulating general superconducting circuits. One of the issues is the handling of free modes in the circuit, that is, circuit modes with no potential term in the Hamiltonian. Another issue is circuit size, namely the challenge of simulating strongly coupled multimode circuits. The main mathematical tool we use to address these issues is the linear canonical transformation in the setting of quantum mechanics. We address the first issue by giving a provably correct algorithm for removing free modes by performing a linear canonical transformation to completely decouple the free modes from other circuit modes. We address the second by giving a series of different linear canonical transformations to reduce intermode couplings, thereby reducing the problem to the weakly coupled case and greatly mitigating the overhead for classical simulation. We benchmark our decoupling methods by applying them to the circuit of two inductively coupled fluxonium qubits, obtaining several orders of magnitude reduction in the size of the Hilbert space that needs to be simulated., Comment: 18 pages, 5 figures

It is believed that random quantum circuits are difficult to simulate classically. These have been used to demonstrate quantum supremacy: the execution of a computational task on a quantum computer that is infeasible for any classical computer. The task underlying the assertion of quantum supremacy by Arute et al. (Nature, 574, 505--510 (2019)) was initially estimated to require Summit, the world's most powerful supercomputer today, approximately 10,000 years. The same task was performed on the Sycamore quantum processor in only 200 seconds. In this work, we present a tensor network-based classical simulation algorithm. Using a Summit-comparable cluster, we estimate that our simulator can perform this task in less than 20 days. On moderately-sized instances, we reduce the runtime from years to minutes, running several times faster than Sycamore itself. These estimates are based on explicit simulations of parallel subtasks, and leave no room for hidden costs. The simulator's key ingredient is identifying and optimizing the "stem" of the computation: a sequence of pairwise tensor contractions that dominates the computational cost. This orders-of-magnitude reduction in classical simulation time, together with proposals for further significant improvements, indicates that achieving quantum supremacy may require a period of continuing quantum hardware developments without an unequivocal first demonstration., Comment: This manuscript subsumes arXiv:1805.01450 and arXiv:1907.11217, significantly improving on both

We report, in a sequence of notes, our work on the Alibaba Cloud Quantum Development Platform (AC-QDP). AC-QDP provides a set of tools for aiding the development of both quantum computing algorithms and quantum processors, and is powered by a large-scale classical simulator deployed on Alibaba Cloud. In this note, we simulate a distance-3 logical qubit encoded in the 17-qubit surface code using experimental noise parameters for transmon qubits in a planar circuit QED architecture. Our simulation features crosstalk induced by ZZ-interactions. We show that at the current-stage noise levels, crosstalk contributes significantly to the dephasing of the logical qubit. This results in a total phase-flip probability of $\sim 0.6\%$, about $60\%$ higher than expected without considering crosstalk. This indicates that for the code considered, the current noise parameters approach, but do not yet meet, the break-even fault-tolerance regime., Comment: 23 pages, 6 figures

We report our work on the Alibaba Cloud Quantum Development Platform (AC-QDP). The capability of AC-QDP's computational engine was already reported in \cite{CZH+18, ZHN+19}.In this follow-up article, we demonstrate with figures how AC-QDP helps in testing large-scale quantum algorithms (currently within the QAOA framework). We give new benchmark results on regular graphs. AC-QDP's QAOA framework can simulate thousands of qubits for up to $4$ layers. Then we discuss two interesting use cases we have implemented on the platform: 1. Optimal QAOA sequences for small-cycle free graphs; 2. Graph structure discovery.

We report, in a sequence of notes, our work on the Alibaba Cloud Quantum Development Platform(AC-QDP). AC-QDP provides a set of tools for aiding the development of both quantum computing algorithms and quantum processors, and is powered by a large-scale classical simulator deployed on Alibaba Cloud. In this note, we report the computational experiments demonstrating the classical simulation capability of AC-QDP. We use as a benchmark the random quantum circuits designed for Google's Bristlecone QPU {\cite{GRCS}}. We simulate Bristlecone-70 circuits with depth $1 + 32 + 1$ in $0.43$ second per amplitude, using $1449$ Alibaba Cloud Elastic Computing Service (ECS) instances, each with $88$ Intel Xeon(Skylake) Platinum 8163 vCPU cores @ 2.5 GHz and $160$ gigabytes of memory. By comparison, the previously best reported results for the same tasks are $104$ and $135$ seconds, using NASA's HPC Pleiades and Electra systems, respectively ({arXiv:1811.09599}). Furthermore, we report simulations of Bristlecone-70 with depth $1+36+1$ and depth $1+40+1$ in $5.6$ and $580.7$ seconds per amplitude, respectively. To the best of our knowledge, these are the first successful simulations of instances at these depths., Comment: 5 pages, 1 figure. Comments are welcome. We renamed our platform to avoid confusion with other products with similar name

We introduce a distributed classical simulation algorithm for general quantum circuits, and present numerical results for calculating the output probabilities of universal random circuits. We find that we can simulate more qubits to greater depth than previously reported using the cluster supported by the Data Infrastructure and Search Technology Division of the Alibaba Group. For example, computing a single amplitude of an $8\times 8$ qubit circuit with depth $40$ was previously beyond the reach of supercomputers. Our algorithm can compute this within $2$ minutes using a small portion ($\approx$ 14% of the nodes) of the cluster. Furthermore, by successfully simulating quantum supremacy circuits of size $9\times 9\times 40$, $10\times 10\times 35 $, $11\times 11\times 31$, and $12\times 12\times 27 $, we give evidence that noisy random circuits with realistic physical parameters may be simulated classically. This suggests that either harder circuits or error-correction may be vital for achieving quantum supremacy from random circuit sampling., Comment: 12 pages, some edits, updated acknowledgements

If a measurement is made on one half of a bipartite system, then, conditioned on the outcome, the other half has a new reduced state. If these reduced states defy classical explanation -- that is, if shared randomness cannot produce these reduced states for all possible measurements -- the bipartite state is said to be steerable. Determining which states are steerable is a challenging problem even for low dimensions. In the case of two-qubit systems a criterion is known for T-states (that is, those with maximally mixed marginals) under projective measurements. In the current work we introduce the concept of keyring models -- a special class of local hidden state models. When the measurements made correspond to real projectors, these allow us to study steerability beyond T-states. Using keyring models, we completely solve the steering problem for real projective measurements when the state arises from mixing a pure two-qubit state with uniform noise. We also give a partial solution in the case when the uniform noise is replaced by independent depolarizing channels., Comment: 15(+4) pages, 5 figures. v2: references added, v3: minor changes

If two quantum players at a nonlocal game G achieve a superclassical score, then their measurement outcomes must be at least partially random from the perspective of any third player. This is the basis for device-independent quantum cryptography. In this paper we address a related question: does a superclassical score at G guarantee that one player has created randomness from the perspective of the other player? We show that for complete-support games, the answer is yes: even if the second player is given the first player's input at the conclusion of the game, he cannot perfectly recover her output. Thus some amount of local randomness (i.e., randomness possessed by only one player) is always obtained when randomness is certified from nonlocal games with quantum strategies. This is in contrast to non-signaling game strategies, which may produce global randomness without any local randomness. We discuss potential implications for cryptographic protocols between mistrustful parties., Comment: This paper is a merge of arXiv:1610.05140 and arXiv:1608.01011. 9 pages

Transversality is a simple and effective method for implementing quantum computation fault-tolerantly. However, no quantum error-correcting code (QECC) can transversally implement a quantum universal gate set (Eastin and Knill, Phys. Rev. Lett., 102, 110502). Since reversible classical computation is often a dominating part of useful quantum computation, whether or not it can be implemented transversally is an important open problem. We show that, other than a small set of non-additive codes that we cannot rule out, no binary QECC can transversally implement a classical reversible universal gate set. In particular, no such QECC can implement the Toffoli gate transversally. We prove our result by constructing an information theoretically secure (but inefficient) quantum homomorphic encryption (ITS-QHE) scheme inspired by Ouyang et al. (arXiv:1508.00938). Homomorphic encryption allows the implementation of certain functions directly on encrypted data, i.e. homomorphically. Our scheme builds on almost any QECC, and implements that code's transversal gate set homomorphically. We observe a restriction imposed by Nayak's bound (FOCS 1999) on ITS-QHE, implying that any ITS quantum fully homomorphic scheme (ITS-QFHE) implementing the full set of classical reversible functions must be highly inefficient. While our scheme incurs exponential overhead, any such QECC implementing Toffoli transversally would still violate this lower bound through our scheme., Comment: 23 pages, 2 figures, minor edits

A prominent application of quantum cryptography is the distribution of cryptographic keys that are provably secure. Recently, such security proofs were extended by Vazirani and Vidick (Physical Review Letters, 113, 140501, 2014) to the device-independent (DI) scenario, where the users do not need to trust the integrity of the underlying quantum devices. The protocols analyzed by them and by subsequent authors all require a sequential execution of N multiplayer games, where N is the security parameter. In this work, we prove unconditional security of a protocol where all games are executed in parallel. Besides decreasing the number of time-steps necessary for key generation, this result reduces the security requirements for DI-QKD by allowing arbitrary information leakage of each user's inputs within his or her lab. To the best of our knowledge, this is the first parallel security proof for a fully device-independent QKD protocol. Our protocol tolerates a constant level of device imprecision and achieves a linear key rate., Comment: v2: Proofs have been streamlined and reorganized, with minor corrections and numerical adjustments. 33 pages

Cryptographic hash functions are fundamental primitives widely used in practice. For such a function $f:\{0, 1\}^n\to\{0, 1\}^m$, it is nearly impossible for an adversary to produce the hash $f(x)$ without knowing the secret message $x\in\{0, 1\}^n$. Unfortunately, all hash functions are vulnerable under the side-channel attack, which is a grave concern for information security in practice. This is because typically $m\ll n$ and an adversary needs only $m$ bits of information to pass the verification test. In sharp contrast, we show that when quantum states are used, the leakage allowed can be almost the entire secret. More precisely, we call a function that maps $n$ bits to $m$ qubits a quantum cryptographic function if the maximum fidelity between two distinct hashes is negligible in $n$. We show that for any $k=n-\omega(\log n)$, all quantum cryptographic hash functions remain cryptographically secure when leaking $k$ bits of information. By the quantum fingerprinting constructions of Buhrman et al.~({\em Phys. Rev. Lett.} 87, 167902), for all $m=\omega(\log n)$, there exist such quantum cryptographic hash functions. We also show that one only needs $\omega(\log^2 n)$ qubits to verify a quantum cryptographic hash, rather than the whole classical information needed to generate one. Our result also shows that to approximately produce a small amount of quantum side information on a classical secret, it may require almost the full information of the secret. This large gap represents a significant barrier for proving quantum security of classical-proof extractors., Comment: 23 pages

It is known that if two players achieve a superclassical score at a nonlocal game $G$, then their outputs are certifiably random - that is, regardless of the strategy used by the players, a third party will not be able to perfectly predict their outputs (even if he were given their inputs). We prove that for any complete-support game $G$, there is an explicit nonzero function $F_G$ such that if Alice and Bob achieve a superclassical score of $s$ at $G$, then Bob has a probability of at most $1 - F_G ( s )$ of correctly guessing Alice's output after the game is played. Our result implies that certifying global randomness through such games must necessarily introduce local randomness., Comment: 6 pages. Comments welcome

Quantum nonlocality is an inherently non-classical feature of quantum mechanics and manifests itself through violation of Bell inequalities for nonlocal games. We show that in a fairly general setting, a simple extension of a nonlocal game can certify instead the absence of quantum nonlocality. Through contraposition, our result implies that a super-classical performance for such a game ensures that a player's output is unpredictable to the other player. Previously such output unpredictability was known with respect to a third party., Comment: 5 pages

Colbeck (Thesis, 2006) proposed using Bell inequality violations to generate certified random numbers. While full quantum-security proofs have been given, it remains a major open problem to identify the broadest class of Bell inequalities and lowest performance requirements to achieve such security. In this paper, working within the broad class of spot-checking protocols, we prove exactly which Bell inequality violations can be used to achieve full security. Our result greatly improves the known noise tolerance for secure randomness expansion: for the commonly used CHSH game, full security was only known with a noise tolerance of 1.5%, and we improve this to 10.3%. We also generalize our results beyond Bell inequalities and give the first security proof for randomness expansion based on Kochen-Specker inequalities. The central technical contribution of the paper is a new uncertainty principle for the Schatten norm, which is based on the uniform convexity inequality of Ball, Carlen, and Lieb (Inventiones mathematicae, 115:463-482, 1994)., Comment: v3: The main result has been strengthened and the proofs rewritten. The paper now includes a self-contained proof of security under Renyi entropies (simplifying arXiv:1402.0489). 27 pages

How to generate provably true randomness with minimal assumptions? This question is important not only for the efficiency and the security of information processing, but also for understanding how extremely unpredictable events are possible in Nature. All current solutions require special structures in the initial source of randomness, or a certain independence relation among two or more sources. Both types of assumptions are impossible to test and difficult to guarantee in practice. Here we show how this fundamental limit can be circumvented by extractors that base security on the validity of physical laws and extract randomness from untrusted quantum devices. In conjunction with the recent work of Miller and Shi (arXiv:1402:0489), our physical randomness extractor uses just a single and general weak source, produces an arbitrarily long and near-uniform output, with a close-to-optimal error, secure against all-powerful quantum adversaries, and tolerating a constant level of implementation imprecision. The source necessarily needs to be unpredictable to the devices, but otherwise can even be known to the adversary. Our central technical contribution, the Equivalence Lemma, provides a general principle for proving composition security of untrusted-device protocols. It implies that unbounded randomness expansion can be achieved simply by cross-feeding any two expansion protocols. In particular, such an unbounded expansion can be made robust, which is known for the first time. Another significant implication is, it enables the secure randomness generation and key distribution using public randomness, such as that broadcast by NIST's Randomness Beacon. Our protocol also provides a method for refuting local hidden variable theories under a weak assumption on the available randomness for choosing the measurement settings., Comment: A substantial re-writing of V2, especially on model definitions. An abstract model of robustness is added and the robustness claim in V2 is made rigorous. Focuses on quantum-security. A future update is planned to address non-signaling security

Randomness is a vital resource for modern day information processing, especially for cryptography. A wide range of applications critically rely on abundant, high quality random numbers generated securely. Here we show how to expand a random seed at an exponential rate without trusting the underlying quantum devices. Our approach is secure against the most general adversaries, and has the following new features: cryptographic level of security, tolerating a constant level of imprecision in the devices, requiring only a unit size quantum memory per device component for the honest implementation, and allowing a large natural class of constructions for the protocol. In conjunct with a recent work by Chung, Shi and Wu, it also leads to robust unbounded expansion using just 2 multi-part devices. When adapted for distributing cryptographic keys, our method achieves, for the first time, exponential expansion combined with cryptographic security and noise tolerance. The proof proceeds by showing that the Renyi divergence of the outputs of the protocol (for a specific bounding operator) decreases linearly as the protocol iterates. At the heart of the proof are a new uncertainty principle on quantum measurements, and a method for simulating trusted measurements with untrusted devices., Comment: v4: Revised for publication. QKD section substantially revised with corrected and complete proofs. Some reorganization, with appendices added. Minor corrections & changes. 70 pages

Self-testing a quantum device means verifying the existence of a certain quantum state as well as the effect of the associated measurements based only on the statistics of the measurement outcomes. Robust, i.e., error-tolerant, self-testing quantum devices are critical building blocks for quantum cryptographic protocols that rely on imperfect or untrusted quantum devices. We give a criterion which determines whether a given binary XOR game is robust self-testing with the asymptotically optimal error parameter. As an application, we prove that the celebrated CHSH game is an optimally robust self-test. We also prove the same for a family of tests recently proposed by Acin et al. (PRL 108:100402, 2012) for random number generation, thus extending the benefit of the latter tests to allow imperfect or untrusted quantum devices., Comment: 5 pages, plus 29 pages of supporting material. v4: fixed typo in abstract

The well-known Simpson's Paradox, or Yule-Simpson Effect, in statistics is often illustrated by the following thought experiment: A drug may be found in a trial to increase the survival rate for both men and women, but decrease the rate for all the subjects as a whole. This paradoxical reversal effect has been found in numerous datasets across many disciplines, and is now included in most introductory statistics textbooks. In the language of the drug trial, the effect is impossible, however, if both treatment groups' survival rates are higher than both control groups'. Here we show that for quantum probabilities, such a reversal remains possible. In particular, a "quantum drug", so to speak, could be life-saving for both men and women yet deadly for the whole population. We further identify a simple inequality on conditional probabilities that must hold classically but is violated by our quantum scenarios, and completely characterize the maximum quantum violation. As polynomial inequalities on entries of the density operator, our inequalities are of degree 6.

We study the correlation complexity (or equivalently, the communication complexity) of generating a bipartite quantum state $\rho$. When $\rho$ is a pure state, we completely characterize the complexity for approximately generating $\rho$ by a corresponding approximate rank, closing a gap left in Ambainis, Schulman, Ta-Shma, Vazirani and Wigderson (SIAM Journal on Computing, 32(6):1570-1585, 2003). When $\rho$ is a classical distribution $P(x,y)$, we tightly characterize the complexity of generating $P$ by the psd-rank, a measure recently proposed by Fiorini, Massar, Pokutta, Tiwary and de Wolf (STOC 2012). We also present a characterization of the complexity of generating a general quantum state $\rho$., Comment: 12 pages, no figure

The one-shot success probability of a noisy classical channel for transmitting one classical bit is the optimal probability with which the bit can be sent via a single use of the channel. Prevedel et al. (PRL 106, 110505 (2011)) recently showed that for a specific channel, this quantity can be increased if the parties using the channel share an entangled quantum state. We completely characterize the optimal entanglement-assisted protocols in terms of the radius of a set of operators associated with the channel. This characterization can be used to construct optimal entanglement-assisted protocols from the given classical channel and to prove the limit of such protocols. As an example, we show that the Prevedel et al. protocol is optimal for two-qubit entanglement. We also prove some simple upper bounds on the improvement that can be obtained from quantum and no-signaling correlations., Comment: 5 pages, plus 7 pages of supplementary material. v2 is significantly expanded and contains a new result (Theorem 2)

We give algorithms for the optimization problem: $\max_\rho \ip{Q}{\rho}$, where $Q$ is a Hermitian matrix, and the variable $\rho$ is a bipartite {\em separable} quantum state. This problem lies at the heart of several problems in quantum computation and information, such as the complexity of QMA(2). While the problem is NP-hard, our algorithms are better than brute force for several instances of interest. In particular, they give PSPACE upper bounds on promise problems admitting a QMA(2) protocol in which the verifier performs only logarithmic number of elementary gate on both proofs, as well as the promise problem of deciding if a bipartite local Hamiltonian has large or small ground energy. For $Q\ge0$, our algorithm runs in time exponential in $\|Q\|_F$. While the existence of such an algorithm was first proved recently by Brand{\~a}o, Christandl and Yard [{\em Proceedings of the 43rd annual ACM Symposium on Theory of Computation}, 343--352, 2011], our algorithm is conceptually simpler., Comment: 21 pages. Comments are welcome

In this brief report, we consider the equivalence between two sets of $m+1$ bipartite quantum states under local unitary transformations. For pure states, this problem corresponds to the matrix algebra question of whether two degree $m$ matrix polynomials are unitarily equivalent; i.e. $UA_iV^\dagger=B_i$ for $0\leq i\leq m$ where $U$ and $V$ are unitary and $(A_i, B_i)$ are arbitrary pairs of rectangular matrices. We present a randomized polynomial-time algorithm that solves this problem with an arbitrarily high success probability and outputs transforming matrices $U$ and $V$.

The parity decision tree model extends the decision tree model by allowing the computation of a parity function in one step. We prove that the deterministic parity decision tree complexity of any Boolean function is polynomially related to the non-deterministic complexity of the function or its complement. We also show that they are polynomially related to an analogue of the block sensitivity. We further study parity decision trees in their relations with an intermediate variant of the decision trees, as well as with communication complexity., Comment: submitted to TCS on 16-MAR-2009

In our earlier posting "Matrix Pencils and Entanglement Classification", arXiv:0911.1803, we gave a polynomial-time algorithm for deciding if two states in a space of dimension $2\otimes m\otimes n$ are SLOCC equivalent. In this note, we point out that a straightforward modification of the algorithm gives a simple enumeration of all SLOCC equivalence classes in the same space, with the class representatives expressed in the Kronecker canonical normal form of matrix pencils. Thus, two states are equivalent if and only if they have the same canonical form. As an example, we present representatives in canonical form for each of the 26 equivalence classes in $2\otimes 3\otimes n$ systems.

In this paper, we study pure state entanglement in systems of dimension $2\otimes m\otimes n$. Two states are considered equivalent if they can be reversibly converted from one to the other with a nonzero probability using only local quantum resources and classical communication (SLOCC). We introduce a connection between entanglement manipulations in these systems and the well-studied theory of matrix pencils. All previous attempts to study general SLOCC equivalence in such systems have relied on somewhat contrived techniques which fail to reveal the elegant structure of the problem that can be seen from the matrix pencil approach. Based on this method, we report the first polynomial-time algorithm for deciding when two $2\otimes m\otimes n$ states are SLOCC equivalent. Besides recovering the previously known 26 distinct SLOCC equivalence classes in $2\otimes 3\otimes n$ systems, we also determine the hierarchy between these classes.

For a multipartite quantum system of the dimension $d_1\otimes d_2\otimes... d_n$, $d_1\ge d_2\ge...\ge d_n$, is there an entangled state {\em maximum} in the sense that all other states in the system can be obtained from the state through local quantum operations and classical communications (LOCC)? When $d_1\ge\Pi_{i=2}^n d_i$, such state exists. We show that this condition is also necessary. Our proof, somewhat surprisingly, uses results from algebraic complexity theory., Comment: 10 pages, no figure. We know the answer is quite simple, but the proof is somewhat involved. Comments are welcome

We consider the problem of deciding if a given three-party entangled pure state can be converted, with a non-zero success probability, into a given two-party pure state through local quantum operations and classical communication. We show that this question is equivalent to the well-known computational problem of deciding if a multivariate polynomial is identically zero. Efficient randomized algorithms developed to study the latter can thus be applied to the question of tripartite to bipartite entanglement transformations.

We call $F:\{0, 1\}^n\times \{0, 1\}^n\to\{0, 1\}$ a symmetric XOR function if for a function $S:\{0, 1, ..., n\}\to\{0, 1\}$, $F(x, y)=S(|x\oplus y|)$, for any $x, y\in\{0, 1\}^n$, where $|x\oplus y|$ is the Hamming weight of the bit-wise XOR of $x$ and $y$. We show that for any such function, (a) the deterministic communication complexity is always $\Theta(n)$ except for four simple functions that have a constant complexity, and (b) up to a polylog factor, the error-bounded randomized and quantum communication complexities are $\Theta(r_0+r_1)$, where $r_0$ and $r_1$ are the minimum integers such that $r_0, r_1\leq n/2$ and $S(k)=S(k+2)$ for all $k\in[r_0, n-r_1)$., Comment: 9 pages

Understanding the nature of multipartite entanglement is a central mission of quantum information theory. To this end, we investigate the question of tripartite entanglement convertibility. We find that there exists no easy criterion to determine whether a general tripartite transformation can be performed with a nonzero success probability and in fact, the problem is NP-hard. Our results are based on the connections between multipartite entanglement and tensor rank (also called Schmidt rank), a key concept in algebraic complexity theory. Not only does this relationship allow us to characterize the general difficulty in determining possible entanglement transformations, but it also enables us to observe the previously overlooked fact that {\em the Schmidt rank is not an additive entanglement measure}. As a result, we improve some best known transformation rates between specific tripartite entangled states. In addition, we find obtaining the most efficient algorithm for matrix multiplication to be precisely equivalent to determining the optimal rate of conversion between the Greenberger-Horne-Zeilinger state and a triangular distribution of three Einstein-Podolsky-Rosen states., Comment: 5 pages

Suppose that $m$ senders want to transmit classical information to $n$ receivers with zero probability of error using a noisy multipartite communication channel. The senders are allowed to exchange classical, but not quantum, messages among themselves, and the same holds for the receivers. If the channel is classical, a single use can transmit information if and only if multiple uses can. In sharp contrast, we exhibit, for each $m$ and $n$ with $m\ge 2$ or $n\ge 2$, a quantum channel of which a single use is not able to transmit information yet two uses can. This latter property requires and is enabled by quantum entanglement., Comment: 5 pages (actually 4 pages and a bit more, in Revtex 4), 1 eps. Comments are welcome. Don't miss a related work arXiv:0712.3628

A major open problem in communication complexity is whether or not quantum protocols can be exponentially more efficient than classical protocols on _total_ Boolean functions in the two-party interactive model. The answer appears to be ``No''. In 2002, Razborov proved this conjecture for so far the most general class of functions F(x, y) = f(x_1 * y_1, x_2 * y_2, ..., x_n * y_n), where f is a_symmetric_ Boolean function on n Boolean inputs, and x_i, y_i are the i'th bit of x and y, respectively. His elegant proof critically depends on the symmetry of f. We develop a lower-bound method that does not require symmetry and prove the conjecture for a broader class of functions. Each of those functions F(x, y) is obtained by what we call the ``block-composition'' of a ``building block'' g : {0, 1}^k by {0, 1}^k --> {0, 1}, with an f : {0, 1}^n -->{0, 1}, such that F(x, y) = f(g(x_1, y_1), g(x_2, y_2), ..., g(x_n, y_n)), where x_i and y_i are the i'th k-bit block of x and y, respectively. We show that as long as g itself is ``hard'' enough, its block-composition with an_arbitrary_ f has polynomially related quantum and classical communication complexities. Our approach gives an alternative proof for Razborov's result (albeit with a slightly weaker parameter), and establishes new quantum lower bounds. For example, when g is the Inner Product function for k=\Omega(\log n), the_deterministic_ communication complexity of its block-composition with_any_ f is asymptotically at most the quantum complexity to the power of 7.

Many hard algorithmic problems dealing with graphs, circuits, formulas and constraints admit polynomial-time upper bounds if the underlying graph has small treewidth. The same problems often encourage reducing the maximal degree of vertices to simplify theoretical arguments or address practical concerns. Such degree reduction can be performed through a sequence of splittings of vertices, resulting in an _expansion_ of the original graph. We observe that the treewidth of a graph may increase dramatically if the splittings are not performed carefully. In this context we address the following natural question: is it possible to reduce the maximum degree to a constant without substantially increasing the treewidth? Our work answers the above question affirmatively. We prove that any simple undirected graph G=(V, E) admits an expansion G'=(V', E') with the maximum degree <= 3 and treewidth(G') <= treewidth(G)+1. Furthermore, such an expansion will have no more than 2|E|+|V| vertices and 3|E| edges; it can be computed efficiently from a tree-decomposition of G. We also construct a family of examples for which the increase by 1 in treewidth cannot be avoided., Comment: 12 pages, 6 figures, the main result used by quant-ph/0511070

Bennett et al. \cite{BDF+99} identified a set of orthogonal {\em product} states in the $3\otimes 3$ Hilbert space such that reliably distinguishing those states requires non-local quantum operations. While more examples have been found for this counter-intuitive ``nonlocality without entanglement'' phenomenon, a complete and computationally verifiable characterization for all such sets of states remains unknown. In this Letter, we give such a characterization for the $3\otimes 3$ space.

We show how to efficiently simulate a quantum many-body system with tree structure when its entanglement is bounded for any bipartite split along an edge of the tree. This is achieved by expanding the {\em time-evolving block decimation} simulation algorithm for time evolution from a one dimensional lattice to a tree graph, while replacing a {\em matrix product state} with a {\em tree tensor network}. As an application, we show that any one-way quantum computation on a tree graph can be efficiently simulated with a classical computer., Comment: 4 pages,7 figures

We initiate the study of quantifying nonlocalness of a bipartite measurement by the minimum amount of classical communication required to simulate the measurement. We derive general upper bounds, which are expressed in terms of certain tensor norms of the measurement operator. As applications, we show that (a) If the amount of communication is constant, quantum and classical communication protocols with unlimited amount of shared entanglement or shared randomness compute the same set of functions; (b) A local hidden variable model needs only a constant amount of communication to create, within an arbitrarily small statistical distance, a distribution resulted from local measurements of an entangled quantum state, as long as the number of measurement outcomes is constant., Comment: A preliminary version of this paper appears as part of an article in Proceedings of the the 37th ACM Symposium on Theory of Computing (STOC 2005), 460--467, 2005

The treewidth of a graph is a useful combinatorial measure of how close the graph is to a tree. We prove that a quantum circuit with $T$ gates whose underlying graph has treewidth $d$ can be simulated deterministically in $T^{O(1)}\exp[O(d)]$ time, which, in particular, is polynomial in $T$ if $d=O(\log T)$. Among many implications, we show efficient simulations for log-depth circuits whose gates apply to nearby qubits only, a natural constraint satisfied by most physical implementations. We also show that one-way quantum computation of Raussendorf and Briegel (Physical Review Letters, 86:5188--5191, 2001), a universal quantum computation scheme with promising physical implementations, can be efficiently simulated by a randomized algorithm if its quantum resource is derived from a small-treewidth graph., Comment: 7 figures

We investigate the randomized and quantum communication complexity of the Hamming Distance problem, which is to determine if the Hamming distance between two n-bit strings is no less than a threshold d. We prove a quantum lower bound of \Omega(d) qubits in the general interactive model with shared prior entanglement. We also construct a classical protocol of O(d \log d) bits in the restricted Simultaneous Message Passing model, improving previous protocols of O(d^2) bits (A. C.-C. Yao, Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing, pp. 77-81, 2003), and O(d\log n) bits (D. Gavinsky, J. Kempe, and R. de Wolf, quant-ph/0411051, 2004)., Comment: 8 pages, v3, updated reference. to appear in Information Processing Letters, 2006

We propose an approach for quantifying a quantum circuit's quantumness as a means to understand the nature of quantum algorithmic speedups. Since quantum gates that do not preserve the computational basis are necessary for achieving quantum speedups, it appears natural to define the quantumness of a quantum circuit using the number of such gates. Intuitively, a reduction in the quantumness requires an increase in the amount of classical computation, hence giving a ``quantum and classical tradeoff''. In this paper we present two results on this direction. The first gives an asymptotic answer to the question: ``what is the minimum number of non-basis-preserving gates required to generate a good approximation to a given state''. This question is the quantum analogy of the following classical question, ``how many fair coins are needed to generate a given probability distribution'', which was studied and resolved by Knuth and Yao in 1976. Our second result shows that any quantum algorithm that solves Grover's Problem of size n using k queries and l levels of non-basis-preserving gates must have k*l=\Omega(n).