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

ON THE quantum complexity OF EVALUATING THE TUTTE POLYNOMIAL

JOURNAL OF KNOT THEORY AND ITS RAMIFICATIONS 2010年第6期19卷 727-737页

作者： Ahmadi, Hamed Wocjan, Pawel Univ Cent Florida Dept Math Orlando FL 32816 USA Univ Cent Florida Sch Elect Engn & Comp Sci Orlando FL 32816 USA

We show that the problem of approximately evaluating the Tutte polynomial of triangular graphs at the points (q, 1/q) of the Tutte plane is BQP-complete for (most) roots of unity q. We also consider circular graphs and show that the problem of approximately evaluating the Tutte polynomial of these graphs at the point (e(2 pi i/5), e(-2 pi i/5)) is DQC1-complete and at points (q(k), 1 + 1-q(-k)/(q(1/2)-q(-1/2))(2)) for some integer k is in BQP. To show that these problems can be solved by a quantum computer, we rely on the relation of the Tutte polynomial of a planar G graph with the Jones and HOMFLY polynomial of the alternating link D(G) given by the medial graph of G. In the case of our graphs the corresponding links are equal to the plat and trace closures of braids. It is known how to evaluate the Jones and HOMFLY polynomial for closures of braids. To establish the hardness results, we use the property that the images of the generators of the braid group under the irreducible Jones-Wenzl representations of the Hecke algebra have finite order. We show that for each braid b we can efficiently construct a braid (b) over tilde such that the evaluation of the Jones and HOMFLY polynomials of their closures at a fixed root of unity leads to the same value and that the closures of (b) over tilde are alternating links.

关键词： quantum algorithm quantum complexity Tutte polynomial link invariants

来源：评论

学校读者我要写书评

暂无评论

Towards a Geometrization of quantum complexity and Chaos 1

引用

5th International Conference on Geometric Science of Information (GSI)

作者： Rattacaso, Davide Vitale, Patrizia Hamma, Alioscia Univ Napoli Federico II Dipartimento Fis Ettore Pancini Via Cinthia I-80126 Naples NA Italy Ist Nazl Fis Nucl Sez Napoli Via Cinthia Naples NA Italy Univ Massachusetts Phys Dept Boston MA 02125 USA

ISBN: (数字)9783030802097

ISBN: (纸本)9783030802097;9783030802080

In this paper, we show how the restriction of the quantum Geometric Tensor to manifolds of states that can be generated through local interactions provides a new tool to understand the consequences of locality in physics. After a review of a first result in this context, consisting in a geometric out-of-equilibrium extension of the quantum phase transitions, we argue the opportunity and the usefulness to exploit the quantum Geometric Tensor to geometrize quantum chaos and complexity.

关键词： Geometry of quantum states Local interactions quantum phase transitions quantum complexity quantum chaos

来源：评论

学校读者我要写书评

暂无评论

Microstate distinguishability, quantum complexity, and the eigenstate thermalization hypothesis

引用

CLASSICAL AND quantum GRAVITY 2021年第15期38卷

作者： Bao, Ning Pollack, Jason Wakeham, David Wildenhain, Elizabeth Brookhaven Natl Lab Computat Sci Initiat Upton NY 11973 USA Univ Calif Berkeley Ctr Theoret Phys Berkeley CA 94720 USA Univ Calif Berkeley Dept Phys Berkeley CA 94720 USA Univ British Columbia Dept Phys & Astron Vancouver BC V6T 1Z1 Canada Univ Texas Austin Quantum Informat Ctr Austin TX 78712 USA Univ Texas Austin Dept Comp Sci Austin TX 78712 USA

In this work, we use quantum complexity theory to quantify the difficulty of distinguishing eigenstates obeying the eigenstate thermalization hypothesis (ETH). After identifying simple operators with an algebra of low-energy observables and tracing out the complementary high-energy Hilbert space, the ETH leads to an exponential suppression of trace distance between the coarse-grained eigenstates. Conversely, we show that an exponential hardness of distinguishing between states implies ETH-like matrix elements. The BBBV lower bound on the query complexity of Grover search then translates directly into a complexity-theoretic statement lower bounding the hardness of distinguishing these reduced states.

关键词： eigenstate thermalization hypothesis coarse-graining quantum complexity

来源：评论

学校读者我要写书评

暂无评论

quantum state complexity meets many-body scars

引用

JOURNAL OF PHYSICS-CONDENSED MATTER 2024年第15期36卷 155601-155601页

作者： Nandy, Sourav Mukherjee, Bhaskar Bhattacharyya, Arpan Banerjee, Aritra Jozef Stefan Inst Ljubljana SI-1000 Slovenia UCL Dept Phys & Astron Gower St London WC1E 6BT England Indian Inst Technol Gandhinagar Gandhinagar 382355 Gujarat India Birla Inst Technol & Sci Pilani Campus Jhunjhunu 333031 Rajasthan India Okinawa Inst Sci & Technol 1919-1 Tancha Onna Son Okinawa 9040495 Japan

Scar eigenstates in a many-body system refers to a small subset of non-thermal finite energy density eigenstates embedded into an otherwise thermal spectrum. This novel non-thermal behaviour has been seen in recent experiments simulating a one-dimensional PXP model with a kinetically-constrained local Hilbert space realised by a chain of Rydberg atoms. We probe these small sets of special eigenstates starting from particular initial states by computing the spread complexity associated to time evolution of the PXP hamiltonian. Since the scar subspace in this model is embedded only loosely, the scar states form a weakly broken representation of the Lie algebra. We demonstrate why a careful usage of the forward scattering approximation (FSA), instead of any other method, is required to extract the most appropriate set of Lanczos coefficients in this case as the consequence of this approximate symmetry. Only such a method leads to a well defined notion of a closed Krylov subspace and consequently, that of spread complexity. We show this using three separate initial states, namely |Z2⟩,|Z3⟩ and the vacuum state, due to the disparate classes of scar states hosted by these sectors. We also discuss systematic methods of remedying the imperfections in the FSA setup stemming from these approximate symmetries.

关键词： quantum dynamics quantum many-body scars Rydberg atoms Krylov complexity Lanczos algorithm quantum complexity

来源：评论

学校读者我要写书评

暂无评论

Geodesic derivative in quantum circuit complexity analysis

引用

JOURNAL OF MODERN OPTICS 2010年第19期57卷 1972-1978页

作者： Brandt, Howard E. USA Res Lab Adelphi MD USA

Detailed analysis is given of the geodesic derivative, a useful tool in the Riemannian geometry of quantum computation. The geodesic derivative facilitates numerical evaluation of geodesics describing minimum complexi... 详细信息

关键词： quantum computing quantum circuits quantum complexity Jacobi fields geodesics

来源：评论

学校读者我要写书评

暂无评论

Surveying Structural complexity in quantum Many-Body Systems

引用

JOURNAL OF STATISTICAL PHYSICS 2022年第1期187卷 1-18页

作者： Suen, Whei Yeap Elliott, Thomas J. Thompson, Jayne Garner, Andrew J. P. Mahoney, John R. Vedral, Vlatko Gu, Mile Natl Univ Singapore Ctr Quantum Technol 3 Sci Dr 2 Singapore 117543 Singapore Univ Oxford Dept Phys Clarendon Lab Parks Rd Oxford OX1 3PU England Imperial Coll London Dept Math London SW7 2AZ England Nanyang Technol Univ Sch Phys & Math Sci Singapore 637371 Singapore Nanyang Technol Univ Complex Inst Singapore 637335 Singapore Austrian Acad Sci Inst Quantum Opt & Quantum Informat Boltzmanngasse 3 A-1090 Vienna Austria Univ Calif Davis Complex Sci Ctr One Shields Ave Davis CA 95616 USA Univ Calif Davis Phys Dept One Shields Ave Davis CA 95616 USA Singapore Management Univ Sch Informat Syst 80 Stamford Rd Singapore 178902 Singapore Natl Univ Singapore Dept Phys 3 Sci Dr 2 Singapore 117543 Singapore

quantum many-body systems exhibit a rich and diverse range of exotic behaviours, owing to their underlying non-classical structure. These systems present a deep structure beyond those that can be captured by measures of correlation and entanglement alone. Using tools from complexity science, we characterise such structure. We investigate the structural complexities that can be found within the patterns that manifest from the observational data of these systems. In particular, using two prototypical quantum many-body systems as test cases-the one-dimensional quantum Ising and Bose-Hubbard models-we explore how different information-theoretic measures of complexity are able to identify different features of such patterns. This work furthers the understanding of fully-quantum notions of structure and complexity in quantum systems and dynamics.

关键词： quantum Ising Bose hubbard complexity quantum complexity quantum model Stochastic process

来源：评论

学校读者我要写书评

暂无评论

Classical Simulation and complexity of quantum Computations (Invited Talk)

Classical Simulation and Complexity of Quantum Computations ...

引用

5th International Computer Science Symposium

作者： Jozsa, Richard Univ Cambridge Ctr Math Sci DAMTP Cambridge CB3 0WA England

ISBN: (纸本)9783642131813

quantum computing is widely regarded as being able to offer computational complexity benefits beyond the possibilities of classical computing. Yet the relationship of quantum to classical computational complexity is little understood. A fundamental approach to exploring this issue is to study the extent to which quantum computations (especially with restricted sub-universal ingredients) can be classically efficiently simulated. We will discuss a series of results relating to the classical simulation of some interesting classes of quantum computations, particularly Clifford circuits, matchgate circuits and a simple class of quantum circuits (so-called IQP circuits) comprising commuting gates. We will outline an argument that a suitably efficient classical simulation of the latter class would imply a collapse of the polynomial hierarchy.

关键词： quantum computation quantum complexity classical simulation matchgates

来源：评论

学校读者我要写书评

暂无评论

complexity of Finding and Measuring Ground States in quantum Systems

Complexity of Finding and Measuring Ground States in Quantum...

引用

作者： Meiburg, Alexander Heinz Zhong University of California Santa Barbara

学位级别：Ph.D., Doctor of Philosophy

Given a quantum system that we seek to understand, finding the ground state is often the first and most informative task we can assume, from which we can then examine dynamics, excitations, entanglement geometry, and so on. But there are several different precise senses in which we could ask to ”find the ground state”, and depending on the exact system and the question, the resulting task could be quite easy or difficult. This thesis examines four distinct problems, drawing from a toolkit of Bayesian statistics, the Density Matrix Renormalization Group, convex optimization, Fourier analysis, and computational complexity theory. In one setting, we are given a set of local interactions and asked only, is this Hamiltonian frustrated? This question can be very easy or difficult depending on the types of interactions permitted by the symmetry of the system. We show that in fact there are in fact ”natural” (in a precise, mathematical sense) interaction types of many different difficulties, including complexity classes BQP and QCMA. In the second setting, we have repeatedly measured an unknown quantum state, and we are tasked with determining the most probable state given the measurements. We show that this task is in fact exponentially difficult (NP-hard) in the dimension of the Hilbert space. In the third setting, we examine one-dimensional fermionic systems, and show how Gaussian Fermionic Matrix Product States and DMRG can be combined with Hartree-Fock iteration to find approximate groud states very quickly. In the final setting, we use a quantum computer to perform binary measurements of Green’s functions and wish to reconstruct the whole function. We show that although classical statistical techniques give an acceptable reconstruction, imposing physicality constraints greatly enhances the sample efficiency and reconstruction quality.

关键词： Bayesian Inference Matrix product state quantum complexity Convex optimization Fourier analysis

来源：评论

学校读者我要写书评

暂无评论

complexity MEASURE: A quantum INFORMATION APPROACH

引用

INTERNATIONAL JOURNAL OF quantum INFORMATION 2012年第4期10卷

作者： Campbell-Borges, Yuri Cassio Castilho Piqueira, Jose Roberto Univ Sao Paulo Sch Engn Telecommun & Control Engn Dept BR-05508900 Sao Paulo Brazil

In the past decades, all of the efforts at quantifying systems complexity with a general tool has usually relied on using Shannon's classical information framework to address the disorder of the system through the Boltzmann-Gibbs-Shannon entropy, or one of its extensions. However, in recent years, there were some attempts to tackle the quantification of algorithmic complexities in quantum systems based on the Kolmogorov algorithmic complexity, obtaining some discrepant results against the classical approach. Therefore, an approach to the complexity measure is proposed here, using the quantum information formalism, taking advantage of the generality of the classical-based complexities, and being capable of expressing these systems' complexity on other framework than its algorithmic counterparts. To do so, the Shiner-Davison-Landsberg (SDL) complexity framework is considered jointly with linear entropy for the density operators representing the analyzed systems formalism along with the tangle for the entanglement measure. The proposed measure is then applied in a family of maximally entangled mixed state.

关键词： complexity measure quantum complexity bipartite qubits

来源：评论

学校读者我要写书评

暂无评论

complexity CLASSIFICATION OF LOCAL HAMILTONIAN PROBLEMS

引用

SIAM JOURNAL ON COMPUTING 2016年第2期45卷 268-316页

作者： Cubitt, Toby Montanaro, Ashley UCL Dept Comp Sci Mortimer St London WC1E 6BT England Univ Bristol Sch Math Univ Walk Bristol BS8 1TH Avon England

The calculation of ground-state energies of physical systems can be formalized as the k-LOCAL Hamiltonian problem, which is a natural quantum analogue of classical constraint satisfaction problems. One way of making the problem more physically meaningful is to restrict the Hamiltonian in question by picking its terms from a fixed set S and scaling them by arbitrary weights. Examples of such special cases are the Heisenberg and Ising models from condensed-matter physics. In this work we characterize the complexity of this problem for all 2-local qubit Hamiltonians. Depending on the subset S, the problem falls into one of the following categories: in P;NP-complete;polynomial-time equivalent to the Ising model with transverse magnetic fields;or QMA-complete. The third of these classes has been shown to be StoqMA-complete by Bravyi and Hastings. The characterization holds even if S does not contain any 1-local terms;for example, we prove for the first time QMA-completeness of the Heisenberg and XY interactions in this setting. If S is assumed to contain all 1-local terms, which is the setting considered by previous work, we have a characterization that goes beyond 2-local interactions: for any constant k, all k-local qubit Hamiltonians whose terms are picked from a fixed set S correspond to problems either in P;polynomial-time equivalent to the Ising model with transverse magnetic fields;or QMA-complete. These results are a quantum analogue of the maximization variant of Schaefer's dichotomy theorem for Boolean constraint satisfaction problems.

关键词： quantum complexity quantum computation constraint satisfaction problems local Hamiltonian problem

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：