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

PCP-free APX-Hardness of Nearest Codeword and Minimum Distance

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Bhattiprolu, Vijay Guruswami, Venkatesan Ren, Xuandi Department of Combinatorics & Optimization University of Waterloo Canada Simons Institute for the Theory of Computing Departments of EECS and Mathematics UC Berkeley United States Department of EECS UC Berkeley United States

We give simple deterministic reductions demonstrating the NP-hardness of approximating the nearest codeword problem and minimum distance problem within arbitrary constant factors (and almost-polynomial factors assuming NP cannot be solved in quasipolynomial time). The starting point is a simple NP-hardness result without a gap, and is thus "PCP-free." Our approach is inspired by that of Bhattiprolu and Lee [BL24] who give a PCP-free randomized reduction for similar problems over the integers and the reals. We leverage the existence of Ε-balanced codes to derandomize and further simplify their reduction for the case of finite fields. © 2025, CC BY.

关键词： NP-hard

quantum complexity of the Kronecker coefficients

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Bravyi, Sergey Chowdhury, Anirban Gosset, David Havlíček, Vojtěch Zhu, Guanyu 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

Whether or not the Kronecker coefficients of the symmetric group count some set of combinatorial objects is a longstanding open question. In this work we show that a given Kronecker coefficient is proportional to the rank of a projector that can be measured efficiently using a quantum computer. In other words a Kronecker coefficient counts the dimension of the vector space spanned by the accepting witnesses of a QMA verifier, where QMA is the quantum analogue of NP. This implies that approximating the Kronecker coefficients to within a given relative error is not harder than a certain natural class of quantum approximate counting problems that captures the complexity of estimating thermal properties of quantum many-body systems. A second consequence is that deciding positivity of Kronecker coefficients is contained in QMA, complementing a recent NP-hardness result of Ikenmeyer, Mulmuley and Walter. We obtain similar results for the related problem of approximating row sums of the character table of the symmetric group. Finally, we discuss an efficient quantum algorithm that approximates normalized Kronecker coefficients to inverse-polynomial additive error. Copyright © 2023, The Authors. All rights reserved.

关键词： Vector spaces

Classical simulation of peaked shallow quantum circuits

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Bravyi, Sergey Gosset, David Liu, Yinchen 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 Perimeter Institute for Theoretical Physics Waterloo Canada

An n-qubit quantum circuit is said to be peaked if it has an output probability that is at least inverse-polynomially large as a function of n. We describe a classical algorithm with quasipolynomial runtime nO(log n) that approximately samples from the output distribution of a peaked constant-depth circuit. We give even faster algorithms for circuits composed of nearest-neighbor gates on a D-dimensional grid of qubits, with polynomial runtime nO(1) if D = 2 and almost-polynomial runtime nO(log log n) for D > 2. Our sampling algorithms can be used to estimate output probabilities of shallow circuits to within a given inverse-polynomial additive error, improving previously known methods. As a simple application, we obtain a quasipolynomial algorithm to estimate the magnitude of the expected value of any Pauli observable in the output state of a shallow circuit (which may or may not be peaked). This is a dramatic improvement over the prior state-of-the-art algorithm which had an exponential scaling in √n. Copyright © 2023, The Authors. All rights reserved.

关键词： Timing circuits

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.

关键词：

Classical and quantum algorithms for characters of the symmetric group

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Bravyi, Sergey Gosset, David Havlicek, Vojtech Schatzki, Louis IBM Quantum IBM T.J. Watson Research Center Yorktown HeightsNY10598 United States Department of Combinatorics and Optimization Institute for Quantum Computing University of Waterloo Canada Perimeter Institute for Theoretical Physics Canada University of Illinois Urbana Champaign UrbanaIL61801 United States

Characters of irreducible representations are ubiquitous in group theory. However, computing characters of some groups such as the symmetric group Sn is a challenging problem known to be #P-hard in the worst case. Here we describe a Matrix Product State (MPS) algorithm for characters of Sn. The algorithm computes an MPS encoding all irreducible characters of a given permutation. It relies on a mapping from characters of Sn to quantum spin chains proposed by Crichigno and Prakash. We also provide a simpler derivation of this mapping. We complement this result by presenting a poly(n) size quantum circuit that prepares the corresponding MPS obtaining an efficient quantum algorithm for certain sampling problems based on characters of Sn. To assess classical hardness of these problems we present a general reduction from strong simulation (computing a given probability) to weak simulation (sampling with a small error). This reduction applies to any sampling problem with a certain granularity structure and may be of independent interest. © 2025, CC BY.

关键词： Group theory

On the complexity of sampling from shallow Brownian circuits

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Bentsen, Gregory Fefferman, Bill Ghosh, Soumik Gullans, Michael J. Liu, Yinchen Department of Physics The College of William & Mary United States Department of Computer Science The University of Chicago United States Joint Center for Quantum Information and Computer Science University of Maryland and NIST United States Department of Combinatorics and Optimization University of Waterloo Canada Institute for Quantum Computing University of Waterloo Canada

While many statistical properties of deep random quantum circuits can be deduced, often rigorously and other times heuristically, by an approximation to global Haar-random unitaries, the statistics of constant-depth random quantum circuits are generally less well-understood due to a lack of amenable tools and techniques. We circumvent this barrier by considering a related constant-time Brownian circuit model which shares many similarities with constant-depth random quantum circuits but crucially allows for direct calculations of higher order moments of its output distribution. Using mean-field (large-n) techniques, we fully characterize the output distributions of Brownian circuits at shallow depths and show that they follow a Porter-Thomas distribution, just like in the case of deep circuits, but with a truncated Hilbert space. The access to higher order moments allows for studying the expected and typical Linear Cross-entropy (XEB) benchmark scores achieved by an ideal quantum computer versus the state-of-the-art classical spoofers for shallow Brownian circuits. We discover that for these circuits, while the quantum computer typically scores within a constant factor of the expected value, the classical spoofer suffers from an exponentially larger variance. Numerical evidence suggests that the same phenomenon also occurs in constant-depth discrete random quantum circuits, like those defined over the all-to-all architecture. We conjecture that the same phenomenon is also true for random brickwork circuits in high enough spatial dimension. Copyright © 2024, The Authors. All rights reserved.

关键词： quantum computers

Device-independent uncloneable encryption

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Kundu, Srijita Tan, Ernest Y.-Z. Institute for Quantum Computing Department of Combinatorics and Optimization University of Waterloo WaterlooONN2L 3G1 Canada

Uncloneable encryption, first introduced by Broadbent and Lord (TQC 2020) is a quantum encryption scheme in which a quantum ciphertext cannot be distributed between two non-communicating parties such that, given access to the decryption key, both parties cannot learn the underlying plaintext. In this work, we introduce a variant of uncloneable encryption in which several possible decryption keys can decrypt a particular encryption, and the security requirement is that two parties who receive independently generated decryption keys cannot both learn the underlying ciphertext. We show that this variant of uncloneable encryption can be achieved device-independently, i.e., without trusting the quantum states and measurements used in the scheme, and that this variant works just as well as the original definition in constructing quantum money. Moreover, we show that a simple modification of our scheme yields a single-decryptor encryption scheme, which was a related notion introduced by Georgiou and Zhandry. In particular, the resulting single-decryptor encryption scheme achieves device-independent security with respect to a standard definition of security against random plaintexts. Finally, we derive an "extractor" result for a two-adversary scenario, which in particular yields a single-decryptor encryption scheme for single bit-messages that achieves perfect anti-piracy security without needing the quantum random oracle model. © 2022, CC BY.

关键词： Ciphertext

Generating graph states with a single quantum emitter and the minimum number of fusions

学校读者我要写书评

暂无评论

Physical Review A 2025年第5期111卷 052604-052604页

作者： Matthias C. Löbl Love A. Pettersson Andrew Jena Luca Dellantonio Stefano Paesani Anders S. Sørensen Department of Combinatorics and Optimization University of Waterloo and Institute for Quantum Computing University of Waterloo Ontario Canada Department of Physics and Astronomy University of Exeter Stocker Road Exeter EX4 4QL United Kingdom NNF Quantum Computing Programme Niels Bohr Institute University of Copenhagen Blegdamsvej 17 DK-2100 Copenhagen Ø Denmark

Graph states are the key resources for measurement- and fusion-based quantum computing with photons, yet their creation is experimentally challenging. We optimize a hybrid graph-state generation scheme using a single quantum emitter and linear optics Bell-state measurements called fusions. We first generate a restricted class of states from a single quantum emitter and then apply fusions to create a target graph state, where we use a dynamic programming approach to find the construction that requires the lowest possible number of fusions. Our analysis yields a lookup table for constructing ≈2.8×107 nonisomorphic graph states with the minimum number of fusions. The lookup table covers all graph states with up to eight qubits and several other ones with up to 14 qubits. We present construction protocols of selected graph states and provide the lookup table. For large graph states that are not in the lookup table, we derive bounds for the required number of fusions using graph-theoretic properties. Finally, we use the lookup table to search for the best graph codes for loss-tolerant encodings, given a fixed number of fusions for their construction.

关键词： Qubits

GENERALIZED CUTS AND GROTHENDIECK COVERS: A PRIMAL-DUAL APPROXIMATION FRAMEWORK EXTENDING THE GOEMANS–WILLIAMSON ALGORITHM

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Proença, Nathan Benedetto de Carli Silva, Marcel K. Sato, Cristiane M. Tunçel, Levent Department of Combinatorics and Optimization University of Waterloo Canada Institute of Mathematics and Statistics University of São Paulo Brazil Center for Mathematics Computing and Cognition Federal University of the ABC Region Brazil Canada

We provide a primal-dual framework for randomized approximation algorithms utilizing semidefinite programming (SDP) relaxations. Our framework pairs a continuum of APX-complete problems including MaxCut, Max2Sat, MaxDicut, and more generally, Max-Boolean Constraint Satisfaction and MaxQ (maximization of a positive semidefinite quadratic form over the hypercube) with new APX-complete problems which are stated as convex optimization problems with exponentially many variables. These new dual counterparts, based on what we call Grothendieck covers, range from fractional cut covering problems (for MaxCut) to tensor sign covering problems (for MaxQ). For each of these problem pairs, our framework transforms the randomized approximation algorithms with the best known approximation factors for the primal problems to randomized approximation algorithms for their dual counterparts with reciprocal approximation factors which are tight with respect to the Unique Games Conjecture. For each APX-complete pair, our algorithms solve a single SDP relaxation and generate feasible solutions for both problems which also provide approximate optimality certificates for each other. Our work utilizes techniques from areas of randomized approximation algorithms, convex optimization, spectral sparsification, as well as Chernoff-type concentration results for random matrices. Copyright © 2024, The Authors. All rights reserved.

关键词： Approximation algorithms