An official website of the United States government
Fault-tolerant syndrome extraction is a key ingredient in implementing fault-tolerant quantum computation. While conventional methods use a number of extra qubits that are linear in the weight of the syndrome, several improvements have been introduced using flag gadgets. In this work, we develop a framework to design flag gadgets using classical codes. Using this framework, we show how to perform fault-tolerant syndrome extraction for any stabilizer code with arbitrary distance using exponentially fewer qubits than conventional methods when qubit measurement and reset are relatively slow compared to a round of error correction. In particular, our method requires only ?? flag qubits to fault-tolerantly measure a weight ? stabilizer. We further take advantage of the saving provided by our construction to fault-tolerantly measure multiple stabilizers using a single gadget and show that it maintains the same exponential advantage when it is used to fault-tolerantly extract the syndromes of quantum low-density parity-check codes. Using the developed framework, we perform computer-assisted search to find several small examples where our constructions reduce the number of qubits required. These small examples may be relevant to near-term experiments on small-scale quantum computers.
more »
« less
Quantum advantage in learning from experiments
Quantum technology promises to revolutionize how we learn about the physical world. An experiment that processes quantum data with a quantum computer could have substantial advantages over conventional experiments in which quantum states are measured and outcomes are processed with a classical computer. We proved that quantum machines could learn from exponentially fewer experiments than the number required by conventional experiments. This exponential advantage is shown for predicting properties of physical systems, performing quantum principal component analysis, and learning about physical dynamics. Furthermore, the quantum resources needed for achieving an exponential advantage are quite modest in some cases. Conducting experiments with 40 superconducting qubits and 1300 quantum gates, we demonstrated that a substantial quantum advantage is possible with today’s quantum processors.
more »
« less
- Award ID(s):
- 2103300
- PAR ID:
- 10635693
- Publisher / Repository:
- Science
- Date Published:
- Journal Name:
- Science
- Volume:
- 376
- Issue:
- 6598
- ISSN:
- 0036-8075
- Page Range / eLocation ID:
- 1182 to 1186
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract Due to intense interest in the potential applications of quantum computing, it is critical to understand the basis for potential exponential quantum advantage in quantum chemistry. Here we gather the evidence for this case in the most common task in quantum chemistry, namely, ground-state energy estimation, for generic chemical problems where heuristic quantum state preparation might be assumed to be efficient. The availability of exponential quantum advantage then centers on whether features of the physical problem that enable efficient heuristic quantum state preparation also enable efficient solution by classical heuristics. Through numerical studies of quantum state preparation and empirical complexity analysis (including the error scaling) of classical heuristics, in both ab initio and model Hamiltonian settings, we conclude that evidence for such an exponential advantage across chemical space has yet to be found. While quantum computers may still prove useful for ground-state quantum chemistry through polynomial speedups, it may be prudent to assume exponential speedups are not generically available for this problem.more » « less
-
Quantum Random Access Memory (QRAM) has the potential to revolutionize the area of quantum computing. QRAM uses quantum computing principles to store and modify quantum or classical data efficiently, greatly accelerating a wide range of computer processes. Despite its importance, there is a lack of comprehensive surveys that cover the entire spectrum of QRAM architectures. We fill this gap by providing a comprehensive review of QRAM, emphasizing its significance and viability in existing noisy quantum computers. By drawing comparisons with conventional RAM for ease of understanding, this survey clarifies the fundamental ideas and actions of QRAM. QRAM provides an exponential time advantage compared to its classical counterpart by reading and writing all data at once, which is achieved owing to storage of data in a superposition of states. Overall, we compare six different QRAM technologies in terms of their structure and workings, circuit width and depth, unique qualities, practical implementation, and drawbacks. In general, with the exception of trainable machine learning-based QRAMs, we observe that QRAM has exponential depth/width requirements in terms of the number of qubits/qudits and that most QRAM implementations are practical for superconducting and trapped-ion qubit systems.more » « less
-
We study the problem of observing quantum collective phenomena emerging from large numbers of measurements. These phenomena are difficult to observe in conventional experiments because, in order to distinguish the effects of measurement from dephasing, it is necessary to postselect on sets of measurement outcomes with Born probabilities that are exponentially small in the number of measurements performed. An unconventional approach, which avoids this exponential “postselection problem”, is to construct cross-correlations between experimental data and the results of simulations on classical computers. However, these cross-correlations generally have no definite relation to physical quantities. We first show how to incorporate classical shadows into this framework, thereby allowing for the construction of quantum information-theoretic cross-correlations. We then identify cross-correlations that both upper and lower bound the measurement-averaged von Neumann entanglement entropy, as well as cross-correlations that lower bound the measurement-averaged purity and entanglement negativity. These bounds show that experiments can be performed to constrain postmeasurement entanglement without the need for postselection. To illustrate our technique, we consider how it could be used to observe the measurement-induced entanglement transition in Haar-random quantum circuits. We use exact numerical calculations as proxies for quantum simulations and, to highlight the fundamental limitations of classical memory, we construct cross-correlations with tensor-network calculations at finite bond dimension. Our results reveal a signature of measurement-induced criticality that can be observed using a quantum simulator in polynomial time and with polynomial classical memory. Published by the American Physical Society2024more » « less
-
null (Ed.)Quantum computing is poised to revolutionize some critical intractable computing problems; but to fully take advantage of this computation, computer scientists will need to learn to program in a new way, with new constraints. The challenge in developing a quantum computing curriculum for younger learners is that two dominant approaches, teaching via the underlying quantum physical phenomenon or the mathematical operations that emerge from those phenomenon, require extensive technical knowledge. Our goal is to extract some of the essential insights in the principles of quantum computing and present them in contexts that a broad audience can understand. In this study, we explore how to teach the concept of quantum reversibility. Our interdisciplinary science, science education, computer science education, and computer science team is co-creating quantum computing (QC) learning trajectories (LT), educational materials, and activities for young learners. We present a draft LT for reversibility, the materials that both influenced it and were influenced by it, as well as an analysis of student work and a revised LT. We find that for clear cases, many 8-9 year old students understand reversibility in ways that align with quantum computation. However, when there are less clear-cut cases, students show a level of sophistication in their argumentation that aligns with the rules of reversibility for quantum computing even when their decisions do not match. In particular, students did not utilize the idea of a closed system, analyzing the effects to every item in the system. This blurred the distinction between between reversing (undoing) an action, recycling to reproduce identical items with some of the same materials, or replacing used items with new ones. In addition, some students allowed for not restoring all aspects of the original items, just the ones critical to their core functionality. We then present a revised learning trajectory that incorporates these concepts.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1126/science.abn7293
