检索结果-内蒙古大学图书馆

quantum Advantage from Measurement-Induced Entanglement in Random Shallow Circuits

PRX quantum 2025年第1期6卷 010356-010356页

作者： Adam Bene Watts David Gosset Yinchen Liu Mehdi Soleimanifar Department of Pure Mathematics University of Waterloo Waterloo Ontario Canada N2L 3G1 Institute for Quantum Computing University of Waterloo Waterloo Ontario Canada N2L 3G1 Department of Combinatorics and Optimization University of Waterloo Waterloo Ontario Canada N2L 3G1 Perimeter Institute for Theoretical Physics Waterloo Ontario Canada N2L 2Y5 California Institute of Technology Pasadena California 91125 USA

We study random constant-depth quantum circuits in a two-dimensional (2D) architecture. While these circuits only produce entanglement between nearby qubits on the lattice, long-range entanglement can be generated by measuring a subset of the qubits of the output state. It is conjectured that this long-range measurement-induced entanglement (MIE) proliferates when the circuit depth is at least a constant critical value d∗. For circuits composed of Haar-random two-qubit gates, it is also believed that this coincides with a quantum advantage phase transition in the classical hardness of sampling from the output distribution. Here, we provide evidence for a quantum advantage phase transition in the setting of random Clifford circuits. Our work extends the scope of recent separations between the computational power of constant-depth quantum and classical circuits, demonstrating that this kind of advantage is present in canonical random circuit sampling tasks. In particular, we show that in any architecture of random shallow Clifford circuits, the presence of long-range MIE gives rise to an unconditional quantum advantage. In contrast, any depth-d 2D quantum circuit that satisfies a short-range MIE property can be classically simulated efficiently and with depth O(d). Finally, we introduce a 2D depth-2 “coarse-grained” circuit architecture, composed of random Clifford gates acting on O(log (n)) qubits, for which we prove the existence of long-range MIE and establish an unconditional quantum advantage.

关键词： Qubits

来源：评论

学校读者我要写书评

暂无评论

Rate reduction of blind quantum data compression with local approximations based on the unstable structure of quantum states

引用

Physical Review A 2023年第5期107卷 052421-052421页

作者： Kohdai Kuroiwa Debbie Leung Institute for Quantum Computing University of Waterloo Waterloo Ontario Canada N2L 3G1 Department of Physics and Astronomy University of Waterloo Waterloo Ontario Canada N2L 3G1 Department of Combinatorics and Optimization University of Waterloo Waterloo Ontario Canada N2L 3G1 Perimeter Institute for Theoretical Physics Waterloo Ontario Canada N2L 2Y5

In this paper we propose a protocol for a data compression task, blind quantum data compression, with finite local approximations. The rate of blind data compression is susceptible to approximations even when the approximations are diminutive. This instability originates from the sensitivity of a structure of quantum states against approximations, which makes the analysis of blind compression in the presence of approximations intractable. In this paper we construct a protocol that takes advantage of the instability to reduce the compression rate substantially. Our protocol shows a significant reduction in rate for specific examples we examine. Moreover, we apply our methods to diagonal states and propose two types of approximation methods in this special case. We perform numerical experiments and observe that one of these two approximation methods performs significantly better than the other. Thus, our analysis makes a step toward general investigation of blind quantum data compression with the allowance of approximations towards further investigation of approximation-rate trade-off of blind quantum data compression.

关键词： quantum communication quantum information processing quantum information theory quantum protocols quantum state transfer

来源：评论

学校读者我要写书评

暂无评论

Space-efficient Quantization Method for Reversible Markov Chains

arXiv

引用

arXiv 2022年

作者： Chiang, Chen-Fu Chowdhury, Anirban Wocjan, Pawel Department of Computer and Information Science State University of New York Polytechnic Institute United States Institute for Quantum Computing University of Waterloo Canada Department of Combinatorics and Optimization University of Waterloo Canada Ibm Quantum Ibm T.J. Watson Research Center Yorktown HeightsNY10598 United States

In a seminal paper, Szegedy showed how to construct a quantum walk W(P) for any reversible Markov chain P such that its eigenvector with eigenphase 0 is a quantum sample of the limiting distribution of the random walk and its eigenphase gap is quadratically larger than the spectral gap of P. The standard construction of Szegedy's quantum walk requires an ancilla register of Hilbert-space dimension equal to the size of the state space of the Markov chain. We show that it is possible to avoid this doubling of state space for certain Markov chains that employ a symmetric proposal probability and a subsequent accept/reject probability to sample from the Gibbs distribution. For such Markov chains, we give a quantization method which requires an ancilla register of dimension equal to only the number of different energy values, which is often significantly smaller than the size of the state space. To accomplish this, we develop a technique for block encoding Hadamard products of matrices which may be of wider interest. Copyright © 2022, The Authors. All rights reserved.

关键词： quantum theory

来源：评论

学校读者我要写书评

暂无评论

Optimal lower bounds for quantum Learning via Information Theory

arXiv

引用

arXiv 2023年

作者： Hadiashar, Shima Bab Nayak, Ashwin Sinha, Pulkit Zapata Computing Canada Inc. 25 Adelaide St. East TorontoONM5C 3A1 Canada Department of Combinatorics and Optimization Institute for Quantum Computing University of Waterloo 200 University Ave. W. WaterlooONN2L 3G1 Canada School of Computer Science Institute for Quantum Computing University of Waterloo 200 University Ave. W. WaterlooONN2L 3G1 Canada

Although a concept class may be learnt more efficiently using quantum samples as compared with classical samples in certain scenarios, Arunachalam and de Wolf [3] proved that quantum learners are asymptotically no more efficient than classical ones in the quantum PAC and Agnostic learning models. They established lower bounds on sample complexity via quantum state identification and Fourier analysis. In this paper, we derive optimal lower bounds for quantum sample complexity in both the PAC and agnostic models via an information-theoretic approach. The proofs are arguably simpler, and the same ideas can potentially be used to derive optimal bounds for other problems in quantum learning theory. We then turn to a quantum analogue of the Coupon Collector problem, a classic problem from probability theory also of importance in the study of PAC learning. Arunachalam, Belovs, Childs, Kothari, Rosmanis, and de Wolf [1] characterized the quantum sample complexity of this problem up to constant factors. First, we show that the information-theoretic approach mentioned above provably does not yield the optimal lower bound, at least in its current form. As a by-product, we get a natural ensemble of pure states in arbitrarily high dimensions which are not easily (simultaneously) distinguishable, whereas the ensemble has close to maximal Holevo information. Second, we discover that the information-theoretic approach yields an asymptotically optimal bound for an approximation variant of the problem. Finally, we derive a sharper lower bound for the quantum Coupon Collector problem, via the generalised Holevo-Curlander bounds on the distinguishability of an ensemble. All the aspects of the quantum Coupon Collector problem we study rest on properties of the spectrum of the associated Gram matrix, which may be of independent interest. © 2023, CC BY.

关键词： Information theory

来源：评论

学校读者我要写书评

暂无评论

On the complexity of quantum partition functions

arXiv

引用

arXiv 2021年

作者： Bravyi, Sergey Chowdhury, Anirban Gosset, David Wocjan, Pawel IBM Quantum IBM T.J. Watson Research Center United States Institute for Quantum Computing University of Waterloo Canada Department of Combinatorics and Optimization University of Waterloo Canada

The partition function and free energy of a quantum many-body system determine its physical properties in thermal equilibrium. Here we study the computational complexity of approximating these quantities for n-qubit local Hamiltonians. First, we report a classical algorithm with poly(n) runtime which approximates the free energy of a given 2-local Hamiltonian provided that it satisfies a certain denseness condition. Our algorithm combines the variational characterization of the free energy and convex relaxation methods. It contributes to a body of work on efficient approximation algorithms for dense instances of optimization problems which are hard in the general case, and can be viewed as simultaneously extending existing algorithms for (a) the ground energy of dense 2-local Hamiltonians, and (b) the free energy of dense classical Ising models. Secondly, we establish polynomial-time equivalence between the problem of approximating the free energy of local Hamiltonians and three other natural quantum approximate counting problems, including the problem of approximating the number of witness states accepted by a QMA verifier. These results suggest that simulation of quantum many-body systems in thermal equilibrium may precisely capture the complexity of a broad family of computational problems that has yet to be defined or characterized in terms of known complexity classes. Finally, we summarize state-of-the-art classical and quantum algorithms for approximating the free energy and show how to improve their runtime and memory footprint. Copyright © 2021, The Authors. All rights reserved.

关键词： Free energy

来源：评论

学校读者我要写书评

暂无评论

Every quantum Helps: Operational Advantage of quantum Resources beyond Convexity

引用

Physical Review Letters 2024年第15期132卷 150201-150201页

作者： Kohdai Kuroiwa Ryuji Takagi Gerardo Adesso Hayata Yamasaki Institute for Quantum Computing and Department of Combinatorics and Optimization University of Waterloo Ontario N2L 3G1 Canada Perimeter Institute for Theoretical Physics Ontario N2L 2Y5 Canada Department of Basic Science The University of Tokyo 3-8-1 Komaba Meguro-ku Tokyo 153-8902 Japan School of Mathematical Sciences and Centre for the Mathematical and Theoretical Physics of Quantum Non-Equilibrium Systems University of Nottingham University Park Nottingham NG7 2RD United Kingdom Department of Physics Graduate School of Science The University of Tokyo 7-3-1 Hongo Bunkyo-ku Tokyo 113-0033 Japan

Identifying what quantum-mechanical properties are useful to untap a superior performance in quantum technologies is a pivotal question. quantum resource theories provide a unified framework to analyze and understand such properties, as successfully demonstrated for entanglement and coherence. While these are examples of convex resources, for which quantum advantages can always be identified, many physical resources are described by a nonconvex set of free states and their interpretation has so far remained elusive. Here we address the fundamental question of the usefulness of quantum resources without convexity assumption, by providing two operational interpretations of the generalized robustness measure in general resource theories. First, we characterize the generalized robustness in terms of a nonlinear resource witness and reveal that any state is more advantageous than a free one in some multicopy channel discrimination task. Next, we consider a scenario where a theory is characterized by multiple constraints and show that the generalized robustness coincides with the worst-case advantage in a single-copy channel discrimination setting. Based on these characterizations, we conclude that every quantum resource state shows a qualitative and quantitative advantage in discrimination problems in a general resource theory even without any specification on the structure of the free states.

关键词： quantum channels quantum measurements Resource theories

来源：评论

学校读者我要写书评

暂无评论

The platypus of the quantum channel zoo

arXiv

引用

arXiv 2022年

作者： Leditzky, Felix Leung, Debbie Siddhu, Vikesh Smith, Graeme Smolin, John A. Department of Mathematics IQUIST University of Illinois at Urbana-Champaign United States Institute for Quantum Computing Department of Combinatorics and Optimization University of Waterloo Canada Perimeter Institute for Theoretical Physics Canada JILA University of Colorado Boulder United States Department of Physics & Quantum Computing Group Carnegie Mellon University United States CTQM Department of Physics University of Colorado Boulder United States IBM Quantum IBM T.J. Watson Research Center United States

Understanding quantum channels and the strange behavior of their capacities is a key objective of quantum information theory. Here we study a remarkably simple, low-dimensional, single-parameter family of quantum channels with exotic quantum information-theoretic features. As the simplest example from this family, we focus on a qutrit-to-qutrit channel that is intuitively obtained by hybridizing together a simple degradable channel and a completely useless qubit channel. Such hybridizing makes this channel’s capacities behave in a variety of interesting ways. For instance, the private and classical capacity of this channel coincide and can be explicitly calculated, even though the channel does not belong to any class for which the underlying information quantities are known to be additive. Moreover, the quantum capacity of the channel can be computed explicitly, given a clear and compelling conjecture is true. This "spin alignment conjecture," which may be of independent interest, is proved in certain special cases and additional numerical evidence for its validity is provided. Finally, we generalize the qutrit channel in two ways, and the resulting channels and their capacities display similarly rich behavior. In the companion paper [34], we further show that the qutrit channel demonstrates superadditivity when transmitting quantum information jointly with a variety of assisting channels, in a manner unknown before. Copyright © 2022, The Authors. All rights reserved.

关键词： quantum optics

来源：评论

学校读者我要写书评

暂无评论

Minimal qubit representations of Hamiltonians via conserved charges

arXiv

引用

arXiv 2023年

作者： Gunderman, Lane G. Jena, Andrew Dellantonio, Luca Institute for Quantum Computing University of Waterloo WaterlooONN2L 3G1 Canada Department of Combinatorics and Optimization University of Waterloo WaterlooONN2L 3G1 Canada Department of Physics and Astronomy University of Exeter Stocker Road ExeterEX4 4QL United Kingdom

In the last years, we have been witnessing a tremendous push to demonstrate that quantum computers can solve classically intractable problems. This effort, initially focused on the hardware, progressively included the simplification of the models to be simulated. We consider Hamiltonians written in terms of Pauli operators and systematically cut all qubits that are not essential to simulate the system. Our approach is universally applicable and lowers the complexity by first ensuring that the largest possible portion of the Hilbert space becomes irrelevant, and then by finding and exploiting all conserved charges of the system, i.e., symmetries that can be expressed as Pauli operators. Remarkably, both processes are classically efficient and optimal. To showcase our algorithm, we simplify chemical molecules, lattice gauge theories, the Hubbard and the Kitaev models. Copyright © 2023, The Authors. All rights reserved.

关键词： Hamiltonians

来源：评论

学校读者我要写书评

暂无评论

Robustness- and weight-based resource measures without convexity restriction: Multicopy witness and operational advantage in static and dynamical quantum resource theories

引用

Physical Review A 2024年第4期109卷 042403-042403页

quantum resource theories (QRTs) provide a unified framework to analyze quantum properties as resources for achieving advantages in quantum information processing. The generalized robustness and the weight of resource have been gaining increasing attention as useful resource quantifiers. However, the existing analyses of these measures were restricted to the cases where convexity of the set of free states is assumed, and physically motivated resources do not necessarily satisfy this restriction. In this paper, we give characterizations of robustness- and weight-based measures in general QRTs without convexity restriction through two different yet related approaches. On the one hand, we characterize the generalized robustness and the weight of resource by introducing a nonlinear witness. We show a general construction of new witness observables that detect the resourcefulness of a given state from multiple copies of the state and, using these witnesses, we provide operational interpretations of the above resource measures even without any convexity assumption. On the other hand, we find that the generalized robustness and the weight of resource can also be interpreted as the worst-case maximum advantage in variants of channel-discrimination and channel-exclusion tasks, respectively, where the set of free states consists of several convex subsets corresponding to multiple restrictions. We further extend these results to QRTs for quantum channels and quantum instruments. These characterizations show that every quantum resource exhibits an advantage for the corresponding tasks, even in general QRTs without convexity assumption. Thus, we establish the usefulness of robustness-based and weight-based techniques beyond the conventional scope of convex QRTs, leading to a better understanding of the general structure of QRTs.

关键词： quantum channels quantum measurements Resource theories

来源：评论

学校读者我要写书评

暂无评论

Sample-optimal classical shadows for pure states

arXiv

引用

arXiv 2022年

作者： Grier, Daniel Pashayan, Hakop Schaeffer, Luke Department of Mathematics Department of Computer Science and Engineering UC San Diego United States Institute for Quantum Computing University of Waterloo Canada Department of Combinatorics and Optimization University of Waterloo Canada Perimeter Institute for Theoretical Physics Waterloo Canada Dahlem Center for Complex Quantum Systems Freie Universität Berlin Germany Joint Center for Quantum Information and Computer Science University of Maryland College Park United States

We consider the classical shadows task for pure states in the setting of both joint and independent measurements. The task is to measure few copies of an unknown pure state ρ in order to learn a classical description which suffices to later estimate expectation values of observables. Specifically, the goal is to approximate Tr(Oρ) for any Hermitian observable O to within additive error ϵ provided Tr(O2) ≤ B and O = 1._ Our main result applies to the joint measurement setting, where we show Θ˜(√Bϵ−1 + ϵ−2) samples of ρ are necessary and sufficient to succeed with high probability. The upper bound is a quadratic improvement on the previous best sample complexity known for this problem. For the lower bound, we see that the bottleneck is not how fast we can learn the state but rather how much any classical description of ρ can be compressed for observable estimation. In the independent measurement setting, we show that O(√Bdϵ−1 + ϵ−2) samples suffice. Notably, this implies that the random Clifford measurements algorithm of Huang, Kueng, and Preskill, which is sample-optimal for mixed states, is not optimal for pure states. Interestingly, our result also uses the same random Clifford measurements but employs a different estimator. © 2022, CC BY.

关键词：

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：