Source author record

Yaoyun Shi

Yaoyun Shi appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Catalog footprint

What is connected

22works
13topics
4close collaborators

Actions

Connect this record

Log in to claim

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

22 published item(s)

preprint2022arXiv

Titanium Nitride Film on Sapphire Substrate with Low Dielectric Loss for Superconducting Qubits

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 $μ$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.

preprint2021arXiv

Fluxonium: an alternative qubit platform for high-fidelity operations

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.

preprint2020arXiv

Alibaba Cloud Quantum Development Platform: Surface Code Simulations with Crosstalk

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.

preprint2020arXiv

Classical Simulation of Quantum Supremacy Circuits

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.

preprint2018arXiv

Parallel Device-Independent Quantum Key Distribution

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.

preprint2016arXiv

Robust protocols for securely expanding randomness and distributing keys using untrusted quantum devices

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.

preprint2015arXiv

Physical Randomness Extractors: Generating Random Numbers with Minimal Assumptions

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.

preprint2013arXiv

Optimal robust quantum self-testing by binary nonlocal XOR games

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.

preprint2012arXiv

Correlation/Communication complexity of generating bipartite states

We study the correlation complexity (or equivalently, the communication complexity) of generating a bipartite quantum state $ρ$. When $ρ$ is a pure state, we completely characterize the complexity for approximately generating $ρ$ 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 $ρ$ 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 $ρ$.

preprint2012arXiv

On optimal entanglement assisted one-shot classical communication

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.

preprint2012arXiv

Quantum Simpsons Paradox and High Order Bell-Tsirelson Inequalities

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.

preprint2011arXiv

Epsilon-net method for optimizations over separable states

We give algorithms for the optimization problem: $\max_ρ\ip{Q}ρ$, where $Q$ is a Hermitian matrix, and the variable $ρ$ 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{ã}o, Christandl and Yard [{\em Proceedings of the 43rd annual ACM Symposium on Theory of Computation}, 343--352, 2011], our algorithm is conceptually simpler.

preprint2010arXiv

Deciding Unitary Equivalence Between Matrix Polynomials and Sets of Bipartite Quantum States

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$.

preprint2010arXiv

On the parity complexity measures of Boolean functions

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.

preprint2009arXiv

Matrix Pencils and Entanglement Classification

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.

preprint2009arXiv

Tripartite to Bipartite Entanglement Transformations and Polynomial Identity Testing

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.

preprint2007arXiv

Constant-degree graph expansions that preserve the treewidth

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.

preprint2007arXiv

Tensor Norms and the Classical Communication Complexity of Nonlocal Quantum Measurement

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.

preprint2006arXiv

The Communication Complexity of the Hamming Distance Problem

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 Ω(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).

preprint2003arXiv

Quantum and Classical Tradeoffs

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=Ω(n).

preprint2001arXiv

Quantum complexities of ordered searching, sorting, and element distinctness

We consider the quantum complexities of the following three problems: searching an ordered list, sorting an un-ordered list, and deciding whether the numbers in a list are all distinct. Letting N be the number of elements in the input list, we prove a lower bound of \frac{1}π(\ln(N)-1) accesses to the list elements for ordered searching, a lower bound of Ω(N\log{N}) binary comparisons for sorting, and a lower bound of Ω(\sqrt{N}\log{N}) binary comparisons for element distinctness. The previously best known lower bounds are {1/12}\log_2(N) - O(1) due to Ambainis, Ω(N), and Ω(\sqrt{N}), respectively. Our proofs are based on a weighted all-pairs inner product argument. In addition to our lower bound results, we give a quantum algorithm for ordered searching using roughly 0.631 \log_2(N) oracle accesses. Our algorithm uses a quantum routine for traversing through a binary search tree faster than classically, and it is of a nature very different from a faster algorithm due to Farhi, Goldstone, Gutmann, and Sipser.

preprint2001arXiv

Quantum lower bounds for the collision and the element distinctness problems

Given a function f as an oracle, the collision problem is to find two distinct inputs i and j such that f(i)=f(j), under the promise that such inputs exist. Since the security of many fundamental cryptographic primitives depends on the hardness of finding collisions, quantum lower bounds for the collision problem would provide evidence for the existence of cryptographic primitives that are immune to quantum cryptanalysis. In this paper, we prove that any quantum algorithm for finding a collision in an r-to-one function must evaluate the function Omega((n/r)^{1/3}) times, where n is the size of the domain and r|n. This improves the previous best lower bound of Omega((n/r)^{1/5}) evaluations due to Aaronson [quant-ph/0111102], and is tight up to a constant factor. Our result also implies a quantum lower bound of Omega(n^{2/3}) queries to the inputs for the element distinctness problem, which is to determine whether or not the given n real numbers are distinct. The previous best lower bound is Omega(sqrt{n}} queries in the black-box model; and Omega(sqrt{n}log{n}) comparisons in the comparisons-only model, due to Høyer, Neerbek, and Shi [ICALP'01, quant-ph/0102078].