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

Beating Classical Impossibility of Position Verification 13

学校读者我要写书评

暂无评论

Beating Classical Impossibility of Position Verification

13th Innovations in Theoretical computer science Conference, ITCS 2022

作者： Liu, Jiahui Liu, Qipeng Qian, Luowen Department of Computer Science University of Texas AustinTX United States Simons Institute for the Theory of Computing BerkeleyCA United States Department of Computer Science Boston University MA United States

ISBN: (纸本)9783959772174

Chandran et al. (SIAM J. Comput.'14) formally introduced the cryptographic task of position verification, where they also showed that it cannot be achieved by classical protocols. In this work, we initiate the study of position verification protocols with classical verifiers. We identify that proofs of quantumness (and thus computational assumptions) are necessary for such position verification protocols. For the other direction, we adapt the proof of quantumness protocol by Brakerski et al. (FOCS'18) to instantiate such a position verification protocol. As a result, we achieve classically verifiable position verification assuming the quantum hardness of Learning with Errors. Along the way, we develop the notion of 1-of-2 non-local soundness for a natural non-local game for 1-of-2 puzzles, first introduced by Radian and Sattath (AFT'19), which can be viewed as a computational unclonability property. We show that 1-of-2 non-local soundness follows from the standard 2-of-2 soundness (and therefore the adaptive hardcore bit property), which could be of independent interest. © Jiahui Liu, Qipeng Liu, and Luowen Qian;licensed under Creative Commons License CC-BY 4.0

关键词： quantum cryptography

Successive Cancellation Sampling Decoder: An Attempt to Analyze List Decoding Theoretically

学校读者我要写书评

暂无评论

Successive Cancellation Sampling Decoder: An Attempt to Anal...

IEEE International Symposium on Information theory

作者： Hsin-Po Wang Venkatesan Guruswami Department of Electrical Engineering and Computer Science Simons Institute for the Theory of Computing University of California Berkeley Berkeley CA USA

ISBN: (数字)9798350382846

ISBN: (纸本)9798350382853

Successive cancellation list (SCL) decoders of polar codes excel in practical performance but pose challenges for theoretical analysis. Existing works either limit their scope to erasure channels or address general channels without taking advantage of soft information. In this paper, we propose the successive cancellation sampling (SCS) decoder. SCS hires iid “agents” to sample codewords using posterior probabilities. This makes it fully parallel and amenable for some theoretical analysis. As an example, when comparing SCS with $\boldsymbol{a}$ agents to any list decoder with list size $\boldsymbol{\ell}$ , we can prove that the error probability of the former is at most $\boldsymbol{\ell}/\boldsymbol{ae}$ more than that of the latter. In this paper, we also describe how to adjust the “temperature” of agents. Warmer agents are less likely to sample the same codewords and hence can further reduce error probability.

关键词： Convolutional codes Error probability Posterior probability Picture archiving and communication systems Decoding Polar codes

Super-exponential quantum advantage for finding the center of a sphere

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Li, Guanzhong Li, Lvzhou Institute of Quantum Computing and Software School of Computer Science and Engineering Sun Yat-sen University Guangzhou510006 China

This article considers the geometric problem of finding the center of a sphere in vector space over finite fields, given samples of random points on the sphere. We propose a quantum algorithm based on continuous-time quantum walks that needs only a constant number of samples to find the center. We also prove that any classical algorithm for the same task requires approximately as many samples as the dimension of the vector space, by a reduction to an old and basic algebraic result—Warning’s second theorem. Thus, a super-exponential quantum advantage is revealed for the first time for a natural and intuitive geometric problem. © 2024, CC BY.

关键词： Spheres

Tolerant quantum Junta Testing

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Chen, Zhaoyang Li, Lvzhou Luo, Jingquan Institute of Quantum Computing and Software School of Computer Science and Engineering Sun Yat-sen University Guangzhou510006 China

Junta testing for Boolean functions has sparked a long line of work over recent decades in theoretical computer science, and recently has also been studied for unitary operators in quantum computing. Tolerant junta testing is more general and challenging than the standard version. While optimal tolerant junta testers have been obtained for Boolean functions, there has been no knowledge about tolerant junta testers for unitary operators, which was thus left as an open problem in [Chen, Nadimpalli, and Yuen, SODA2023]. In this paper, we settle this problem by presenting the first algorithm to decide whether a unitary is ϵ1-close to some quantum k-junta or is ϵ2-far from any quantum k-junta, where an n-qubit unitary U is called a quantum k-junta if it only non-trivially acts on just k of the n qubits. More specifically, we present a tolerant tester with (Equation presented), and ρ ∈ (0, 1), and the query complexity is (Equation presented), which demonstrates a trade-off between the amount of tolerance and the query complexity. Note that our algorithm is non-adaptive which is preferred over its adaptive counterparts, due to its simpler as well as highly parallelizable nature. At the same time, our algorithm does not need access to U†, whereas this is usually required in the literature. © 2024, CC BY.

关键词： Boolean functions

Implementation of Continuous-Time quantum Walk on Sparse Graph

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Chen, Zhaoyang Li, Guanzhong Li, Lvzhou Institute of Quantum Computing and Software School of Computer Science and Engineering Sun Yat-sen University Guangzhou510006 China

Continuous-time quantum walks (CTQWs) play a crucial role in quantum computing, especially for designing quantum algorithms. However, how to efficiently implement CTQWs is a challenging issue. In this paper, we study implementation of CTQWs on sparse graphs, i.e., constructing efficient quantum circuits for implementing the unitary operator e−iHt, where H = γA (γ is a constant and A corresponds to the adjacency matrix of a graph). Our result is, for a d-sparse graph with N vertices and evolution time t, we can approximate e−iHt by a quantum circuit with gate complexity (d3||H||tN log N)1+o(1), compared to the general Pauli decomposition, which scales like (||H||tN4 log N)1+o(1). For sparse graphs, for instance, d = O(1), we obtain a noticeable improvement. Interestingly, our technique is related to graph decomposition. More specifically, we decompose the graph into a union of star graphs, and correspondingly, the Hamiltonian H can be represented as the sum of some Hamiltonians Hj, where each e−iHjt is a CTQW on a star graph which can be implemented efficiently. © 2024, CC BY.

关键词： quantum computers

Second moment of Hafnians in Gaussian boson sampling

学校读者我要写书评

暂无评论

Physical Review A 2025年第4期111卷 042412-042412页

作者： Adam Ehrenberg Joseph T. Iosue Abhinav Deshpande Dominik Hangleiter Alexey V. Gorshkov Joint Center for Quantum Information and Computer Science NIST/University of Maryland College Park Maryland 20742 USA Joint Quantum Institute NIST/University of Maryland College Park Maryland 20742 USA IBM Quantum Almaden Research Center San Jose California 95120 USA Simons Institute for the Theory of Computing University of California at Berkeley Berkeley California 94720 USA

Gaussian boson sampling is a popular method for experimental demonstrations of quantum advantage, but many subtleties remain in fully understanding its theoretical underpinnings. An important component in the theoretical arguments for approximate average-case hardness of sampling is anticoncentration, which is a second-moment property of the output probabilities. In Gaussian boson sampling these are given by hafnians of generalized circular orthogonal ensemble matrices. In a companion work by Ehrenberg et al. [Phys. Rev. Lett. 134, 140601 (2025)], we develop a graph-theoretic method to study these moments and use it to identify a transition in anticoncentration. In this work, we find a recursive expression for the second moment using these graph-theoretic techniques. While we have not been able to solve this recursion by hand, we are able to solve it numerically exactly, which we do up to Fock sector 2n=80. We further derive analytical results about the second moment. These results allow us to pinpoint the transition in anticoncentration and furthermore yield the expected linear cross-entropy benchmarking score for an ideal (error-free) device.

关键词： Graph theory

Production of exotic hadrons in pp and nuclear collisions

学校读者我要写书评

暂无评论

Nuclear science and Techniques 2025年第4期36卷 1-22页

作者： Jin-Hui Chen Feng-Kun Guo Yu-Gang Ma Cheng-Ping Shen Qi-Ye Shou Qian Wang Jia-Jun Wu Bing-Song Zou Key Laboratory of Nuclear Physics and Ion-beam Application(MOE) Institute of Modern PhysicsFudan UniversityShanghai 200433China Shanghai Research Center for Theoretical Nuclear Physics NSFC and Fudan UniversityShanghai 200438China CAS Key Laboratory of Theoretical Physics Institute of Theoretical PhysicsChinese Academy of SciencesBeijing 100190China School of Physical Sciences University of Chinese Academy of SciencesBeijing 100049China Peng Huanwu Collaborative Center for Research and Education Beihang UniversityBeijing 100191China Southern Center for Nuclear-Science Theory(SCNT) Institute of Modern PhysicsChinese Academy of SciencesHuizhou 516000China Guangdong-Hong Kong Joint Laboratory of Quantum Matter Guangdong Provincial Key Laboratory of Nuclear ScienceSouthern Nuclear Science Computing CenterSouth China Normal UniversityGuangzhou 510006China Key Laboratory of Atomic and Subatomic Structure and Quantum Control(MOE) Guangdong Basic Research Center of Excellence for Structure and Fundamental Interactions of MatterInstitute of Quantum MatterSouth China Normal UniversityGuangzhou 510006China Department of Physics Tsinghua UniversityBeijing 100084China

Exotic hadrons,beyond the conventional quark model,have been discovered over the past two *** these states can lead to a deeper understanding of the nonperturbative dynamics of the strong *** this review,we focus on the production of exotic hadrons in pp,PP^(-),and nuclear *** observations of light and hypernuclei as prototypes of hadronic molecules in heavy-ion collisions are also briefly discussed.

关键词： Exotic hadrons Hadron-hadron collision Heavy-ion collision

Circuit Complexity of Sparse quantum State Preparation

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Luo, Jingquan Li, Lvzhou Institute of Quantum Computing and Software School of Computer Science and Engineering Sun Yat-sen University Guangzhou510006 China

quantum state preparation is a fundamental and significant subroutine in quantum computing. In this paper, we conduct a systematic investigation on the circuit size for sparse quantum state preparation. A quantum state is said to be d-sparse if it has only d non-zero amplitudes. For the task of preparing an n-qubit d-sparse quantum state, we obtain the following results: • Without ancillary qubits: We propose the first approach that uses o(dn) elementary gates without using ancillary qubits. Specifically, it is proven that any n-qubit d-sparse quantum state can be prepared by a quantum circuit of size O(logdnn +n) without using ancillary qubits. This is asymptotically optimal when d = poly(n), and this optimality extends to a broader scope under some reasonable assumptions. • With limited ancillary qubits: (i) We show that any n-qubit d-sparse quantum state can be prepared by a quantum circuit of size O(logdnd) and depth Θ(log dn) using at most O(logndd) ancillary qubits, which not only reduces the circuit size compared to the one without ancillary qubits when d = ω(poly(n)), but also achieves the same asymptotically optimal depth while utilizing fewer ancillary qubits and applying fewer quantum gates compared to the result given in [Physical Review Letters, 129, 230504(2022)]. (ii) We establish the lower bound Ω(log(n+dnm)+log d + n) on the circuit size with m ancillary qubits available. Additionally, we demonstrate a slightly stronger lower bound Ω(log(dnn+m) + n) under reasonable assumptions. • With unlimited ancillary qubits: We prove that with arbitrary amount of ancillary qubits available, the circuit size for preparing n-qubit d-sparse quantum states is Θ(logdndn + n). © 2024, CC BY.

关键词： Qubits

LazyDB: I/O Optimization of Blockchain Storage System Based on Non-Volatile Memory 4

学校读者我要写书评

暂无评论

LazyDB: I/O Optimization of Blockchain Storage System Based ...

4th International Conference on Information science, Parallel and Distributed Systems, ISPDS 2023

作者： Liu, Yang Ge, Xuran Xiao, Nong Chen, Zhiguang Ou, Yang Institute for Quantum Information College of Computer National University of Defense Technology State Key Laboratory of High-Performance Computing Changsha China School of Computer Science and Engineering Sun Yat-sen University Guangzhou China College of Computer National University of Defense Technology Changsha China

ISBN: (纸本)9798350337181

For the blockchain storage system, this paper proposes an I/O optimization scheme based on non-volatile memory based on the storage performance requirements of the blockchain system application. This scheme adopts the key-value separation strategy. Due to the uncertain size of transaction data, by separating the 'key' and 'value' of transaction data, the inherent read-write amplification problem of the LSM-Tree structure is solved. The key-value separation strategy redesigns the storage system's space management and garbage collection mechanisms. Therefore, this chapter uses the byte-addressing characteristics of non-volatile memory to build a new data storage structure, a lazy compression mechanism, and a lazy garbage collection mechanism. On this basis, this paper builds a LazyDB database system for blockchain storage. To ensure the safe and reliable operation of the blockchain system, it can make full use of the storage medium and data characteristics, reducing the blockchain reading and writing process. The I/O overhead in the storage system improves the storage performance of the system. The experimental results show that compared with the most commonly used databases, such as LevelDB and RocksDB in the blockchain system, LazyDB effectively reduces the write amplification of the system and has higher read, write, and data update performance. © 2023 IEEE.

关键词： Blockchain