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

The Projection Games Conjecture and the hardness of approximation of Super-SAT and related problems

学校读者我要写书评

暂无评论

arXiv 2019年

作者： Mukhopadhyay, Priyanka Institute for Quantum Computing Department of Combinatorics and Optimization University of Waterloo 200 University Avenue West WaterlooONN2L 3G1 Canada Centre for Quantum Technologies National University of Singapore

The Super-SAT or SSAT problem was introduced by Dinur et al.[1, 2] to prove the NP-hardness of approximation of two popular lattice problems - Shortest Vector Problem(SVP) and Closest Vector Problem(CVP). They conjectured that SSAT is NP-hard to approximate to within a factor of nc (c > 0 is constant), where n is the size of the SSAT instance. In this paper we prove this conjecture assuming the Projection Games Conjecture(PGC), given by Moshkovitz[3]. This implies hardness of approximation of SVP and CVP within polynomial factors, assuming PGC. We also reduce SSAT to the Nearest Codeword Problem(NCP) and Learning Halfspace Problem(LHP), as considered by Arora et al.[4]. This proves that both these problems are NP-hard to approximate within a factor of Nc′/log log n(c′ > 0 is constant) where N is the size of the instances of the respective problems. Assuming PGC these problems are proved to be NP-hard to approximate within polynomial factors. © 2019, CC BY-NC-ND.

关键词： Vectors

How to simulate quantum measurement without computing marginals

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Bravyi, Sergey Gosset, David Liu, Yinchen IBM Quantum IBM T.J. Watson Research Center United States Department of Combinatorics and Optimization University of Waterloo Canada Institute for Quantum Computing University of Waterloo Canada Perimeter Institute for Theoretical Physics Waterloo Canada

We describe and analyze algorithms for classically simulating measurement of an n-qubit quantum state ψ in the standard basis, that is, sampling a bit string x from the probability distribution |〈x|ψ〉|2. Our algorithms reduce the sampling task to computing poly(n) amplitudes of n-qubit states;unlike previously known techniques they do not require computation of marginal probabilities. First we consider the case where |ψ〉 = U|0n〉is the output state of an m-gate quantum circuit U. We propose an exact sampling algorithm which involves computing O(m) amplitudes of n-qubit states generated by subcircuits of U spanned by the first t = 1, 2,..., m gates. We show that our algorithm can significantly accelerate quantum circuit simulations based on tensor network contraction methods or low-rank stabilizer decompositions. As another striking consequence we obtain an efficient classical simulation algorithm for measurement-based quantum computation with the surface code resource state on any planar graph, generalizing a previous algorithm which was known to be efficient only under restrictive topological constraints on the ordering of single-qubit measurements. Second, we consider the case in which ψ is the unique ground state of a local Hamiltonian with a spectral gap that is lower bounded by an inverse polynomial function of n. We prove that a simple Metropolis-Hastings Markov Chain mixes rapidly to the desired probability distribution provided that ψ obeys a certain technical condition, which we show is satisfied for all sign-problem free Hamiltonians. This gives a sampling algorithm which involves computing poly(n) amplitudes of ψ. Copyright © 2021, The Authors. All rights reserved.

关键词： Probability distributions

Number-Theoretic Nature of Communication in quantum Spin Systems

学校读者我要写书评

暂无评论

Physical Review Letters 2012年第5期109卷 050502-050502页

作者： Chris Godsil Stephen Kirkland Simone Severini Jamie Smith Combinatorics & Optimization University of Waterloo N2L 3G1 Waterloo Canada Hamilton Institute National University of Ireland Maynooth County Kildare Ireland Department of Computer Science and Department of Physics & Astronomy University College London WC1E 6BT London United Kingdom Institute for Quantum Computing and Combinatorics & Optimization University of Waterloo N2L 3G1 Waterloo Canada

The last decade has witnessed substantial interest in protocols for transferring information on networks of quantum mechanical objects. A variety of control methods and network topologies have been proposed, on the basis that transfer with perfect fidelity—i.e., deterministic and without information loss—is impossible through unmodulated spin chains with more than a few particles. Solving the original problem formulated by Bose [Phys. Rev. Lett. 91, 207901 (2003)], we determine the exact number of qubits in unmodulated chains (with an XY Hamiltonian) that permit transfer with a fidelity arbitrarily close to 1, a phenomenon called pretty good state transfer. We prove that this happens if and only if the number of nodes is n=p−1, 2p−1, where p is a prime, or n=2m−1. The result highlights the potential of quantum spin system dynamics for reinterpreting questions about the arithmetic structure of integers and, in this case, primality.

关键词： KNOWLEDGE transfer (Communication) quantum theory INFORMATION networks NATURAL numbers ARITHMETIC

On the finite convergence of successive SDP relaxation methods

学校读者我要写书评

暂无评论

On the finite convergence of successive SDP relaxation metho...

作者： Kojima, Masakazu Tunçel, Levent Department of Mathematical and Computing Sciences Tokyo Institute of Technology 2-12-1 Oh-Okayama Meguro-ku Tokyo 152-8552 Japan Faculty of Mathematics Department of Combinatorics and Optimization University of Waterloo Waterloo Ont. N2L 3G1 Canada

The fundamental properties related to the finite convergence of the successive semidefinite programming relaxation method proposed by the authors for approximating the convex hull of F were investigated. F was supposed to be a compact subset of the n-dimensional Euclidean space which was described in terms of non empty compact convex subset and a set of quadratic inequalities.

关键词： Operations research

Discovery of resonating integration modes in triple-mode high-amplitude δ Scuti stars: a new evolutionary phase indicator

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Niu, Jia-Shu Xue, Hui-Fang Institute of Theoretical Physics Shanxi University Taiyuan030006 China State Key Laboratory of Quantum Optics Technologies and Devices Shanxi University Taiyuan030006 China Collaborative Innovation Center of Extreme Optics Shanxi University Taiyuan030006 China Department of Physics Taiyuan Normal University Jinzhong030619 China Institute of Computational and Applied Physics Taiyuan Normal University Jinzhong030619 China Shanxi Key Laboratory for Intelligent Optimization Computing and Blockchain Technology Jinzhong030619 China

High-amplitude δ Scuti stars (HADS) that pulsate in their first three radial modes are rare in current samples. Here, we analyse five such triple-mode HADS observed by the Transiting Exoplanet Survey Satellite (TESS) and report that the previously considered second overtone mode (f2) is actually the non-radial component of a resonating integration mode (RI mode, resulting from resonance between a radial p-mode and a non-radial p-g mixed mode), which shows significant amplitude and frequency variations over short timescales (approximately 20 days). This RI mode appears to be widespread among these stars. Notably, all five stars are in the post-main sequence evolutionary phase, actively crossing the Hertzsprung gap. These stars offer valuable insights into stellar evolution during the Hertzsprung gap, which is one of the most rapid evolutionary stages in a star’s life. © 2025, CC BY.

关键词： Image retrieval

An area law for 2D frustration-free spin systems

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Anshu, Anurag Arad, Itai Gosset, David School of Engineering and Applied Sciences Harvard University Cambridge United States Physics Department Technion Israel Institute for Quantum Computing University of Waterloo Canada Department of Combinatorics and Optimization University of Waterloo Canada

We prove that the entanglement entropy of the ground state of a locally gapped frustration-free 2D lattice spin system satisfies an area law with respect to a vertical bipartition of the lattice into left and right regions. We first establish that the ground state projector of any locally gapped frustration-free 1D spin system can be approximated to within error ϵ by a degree O(√n log(ϵ-1)) multivariate polynomial in the interaction terms of the Hamiltonian. This generalizes the optimal bound on the approximate degree of the boolean AND function, which corresponds to the special case of commuting Hamiltonian terms. For 2D spin systems we then construct an approximate ground state projector (AGSP) that employs the optimal 1D approximation in the vicinity of the boundary of the bipartition of interest. This AGSP has sufficiently low entanglement and error to establish the area law using a known technique. Copyright © 2021, The Authors. All rights reserved.

关键词： Ground state

Improved approximation algorithms for bounded-degree local Hamiltonians

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Anshu, Anurag Gosset, David Morenz Korol, Karen J. Soleimanifar, Mehdi Department of EECS Challenge Institute for Quantum Computation University of California Berkeley United States Simons Institute for the Theory of Computing BerkeleyCA United States Department of Combinatorics Optimization and Institute for Quantum Computing University of Waterloo Canada Department of Chemistry University of Toronto Canada Center for Theoretical Physics Massachusetts Institute of Technology United States

We consider the task of approximating the ground state energy of two-local quantum Hamiltonians on bounded-degree graphs. Most existing algorithms optimize the energy over the set of product states. Here we describe a family of shallow quantum circuits that can be used to improve the approximation ratio achieved by a given product state. The algorithm takes as input an n-qubit product state |vi with mean energy e0 = hv|H|vi and variance Var = hv|(H −e0)2|vi, and outputs a state with an energy that is lower than e0 by an amount proportional to Var2/n. In a typical case, we have Var = Ω(n) and the energy improvement is proportional to the number of edges in the graph. When applied to an initial random product state, we recover and generalize the performance guarantees of known algorithms for bounded-occurrence classical constraint satisfaction problems. We extend our results to k-local Hamiltonians and entangled initial states. Copyright © 2021, The Authors. All rights reserved.

关键词： Constraint satisfaction problems

Discovery of resonating integration modes in triple-mode high-amplitude δ Scuti stars: A new evolutionary phase indicator

学校读者我要写书评

暂无评论

Astronomy and Astrophysics 2025年 697卷

关键词： Image retrieval

Rate-Distortion Theory for Mixed States

学校读者我要写书评

暂无评论

Rate-Distortion Theory for Mixed States

IEEE International Symposium on Information Theory

作者： Zahra Baghali Khanian Kohdai Kuroiwa Debbie Leung Munich Center for Quantum Science and Technology & Zentrum Mathematik Technical University of Munich Garching Germany Institute for Quantum Computing University of Waterloo Ontario Canada Department of Combinatorics and Optimization University of Waterloo Perimeter Institute for Theoretical Physics Ontario Canada

In this paper we consider the compression of asymptotically many i.i.d. copies of ensembles of mixed quantum states where the encoder has access to a side information system. This source is equivalently defined as a classical-quantum state, namely, a quantum system correlated with a classical system playing the role of an inaccessible reference system. The figure of merit is evaluated based on per-copy or local error criterion. The rate-distortion theory aims to reveal the trade-off between the compression rate and the per-copy error. The optimal trade-off can be characterized by the rate-distortion function, which is the best rate given a certain distortion. In this paper, we analyze the rate-distortion functions of mixed-state compression. We find the rate-distortion functions in the entanglement-assisted and unassisted scenarios, in terms of a single-letter mutual information quantity and the regularized entanglement of purification, respectively.

关键词：