The problem of matching (exactly or approximately) a pattern P to a walk in an edge labeled graph G = (V, E), denoted PMLG, has received increased attention in recent years. Here we consider conditional lower bounds o...
详细信息
ISBN:
(纸本)9783031206429;9783031206436
The problem of matching (exactly or approximately) a pattern P to a walk in an edge labeled graph G = (V, E), denoted PMLG, has received increased attention in recent years. Here we consider conditional lower bounds on the time complexity of quantumalgorithms for PMLG as well as a new quantum algorithm. We first provide a conditional lower bound based on a reduction from the Longest Common Subsequence problem (LCS) and the recently proposed NC-QSETH. For PMLG under substitutions to the pattern, our results demonstrate (i) that a quantum algorithm running in time O(vertical bar E|m(1-epsilon) + vertical bar E vertical bar(1-epsilon) m) for any constant epsilon > 0 would provide an algorithm for LCS on two strings X and Y running in time (O) over tilde(vertical bar X vertical bar vertical bar Y vertical bar(1-epsilon) + vertical bar X vertical bar(1-epsilon)vertical bar Y vertical bar), which is better than any known quantum algorithm for LCS, and (ii) that a quantum algorithm running in time O(vertical bar E vertical bar m(1/2 - epsilon) + vertical bar E vertical bar(1/2 - epsilon) m) would violate NC-QSETH. Results (i) and (ii) hold even when restricted to binary alphabets for P and the edge labels in G. We then provide a quantum algorithm for all versions of PMLG (exact, only substitutions, and substitutions/insertions/deletions) that runs in time (O) over tilde(root vertical bar V vertical bar vertical bar E vertical bar center dot m). This is an improvement over the classical O(vertical bar E vertical bar m) time algorithm when the graph is non-sparse.
The variational quantum imaginary time-evolution algorithm is efficient in finding the ground state of a quantum Hamiltonian. This algorithm involves solving a system of linear equations in a classical computer and th...
详细信息
The variational quantum imaginary time-evolution algorithm is efficient in finding the ground state of a quantum Hamiltonian. This algorithm involves solving a system of linear equations in a classical computer and the solution is then used to propagate a quantum wave function. Here, we show that owing to the noisy nature of current quantum processors, such a quantum algorithm or the family of quantumalgorithms will require single- and two-qubit gates with very low error probability to produce reliable results. Failure to meet such a condition will result in erroneous quantum data propagation even for a relatively small quantum circuit ansatz. Specifically, we provide the upper bounds on how the relative error in variational parameters’ propagation scales with the probability of noise in quantum hardware. We also present an exact expression of how the relative error in variational parameter propagation scales with the probability of partially depolarizing noise.
We introduce a novel hybrid approach combining tensor network methods with the stabilizer formalism to address the challenges of simulating many-body quantum systems. By integrating these techniques, we enhance our ab...
详细信息
We introduce a novel hybrid approach combining tensor network methods with the stabilizer formalism to address the challenges of simulating many-body quantum systems. By integrating these techniques, we enhance our ability to accurately model unitary dynamics while mitigating the exponential growth of entanglement encountered in classical simulations. We demonstrate the effectiveness of our method through applications to random Clifford T-doped circuits and random Clifford Floquet dynamics. This approach offers promising prospects for advancing our understanding of complex quantum phenomena and accelerating progress in quantum simulation.
In this paper, we study the string matching problem. We design a quantum string-matching algorithm for noisy intermediate-scale quantum (NISQ) computers, given the current leading quantumprocessing units (QPUs) havin...
详细信息
The clever hybridization of quantum computing concepts and evolutionary algorithms (EAs) resulted in a new field called quantum-inspired evolutionary algorithms (QIEAs). Unlike traditional EAs, QIEAs employ quantum bi...
The clever hybridization of quantum computing concepts and evolutionary algorithms (EAs) resulted in a new field called quantum-inspired evolutionary algorithms (QIEAs). Unlike traditional EAs, QIEAs employ quantum bits to adopt a probabilistic representation of the state of a feature in a given solution. This unprecedented feature enables them to achieve better diversity and perform global search, effectively yielding a trade-off between exploration and exploitation. We conducted a comprehensive survey across various publishers and gathered 56 papers published between 2002 and 2024. We thoroughly analyzed these publications, focusing on the novelty elements and types of heuristics employed by the extant quantum-inspired evolutionary algorithms (QIEAs) proposed to solve the feature subset selection (FSS) problem. Importantly, we provided a detailed analysis of the different types of objective functions and popular quantum gates, i.e., rotation gates, employed throughout the literature. Further, we provided merits and demerits of QIEAs vis-à-vis EAs. Additionally, we suggested several open research problems which could be extremely useful to the budding researchers.
Current quantum processors are noisy and have limited coherence and imperfect gate implementations. On such hardware, only algorithms that are shorter than the overall coherence time can be implemented and executed su...
详细信息
Current quantum processors are noisy and have limited coherence and imperfect gate implementations. On such hardware, only algorithms that are shorter than the overall coherence time can be implemented and executed successfully. A good quantum compiler must translate an input program into the most efficient equivalent of itself, getting the most out of the available hardware. In this work, we present novel deterministic algorithms for compiling recurrent quantum circuit patterns in polynomial time. In particular, such patterns appear in quantum circuits that are used to compute the ground-state properties of molecular systems using the variational quantum eigensolver method together with the RyRz heuristic wavefunction Ansatz. We show that our pattern-oriented compiling algorithms, combined with an efficient swapping strategy, produces-in general-output programs that are comparable to those obtained with state-of-the-art compilers, in terms of CNOT count and CNOT depth. In particular, our solution produces unmatched results on RyRz circuits.
Recently, Hosoyamada and Sasaki (Eurocrypt'20) proposed dedicated quantum collision attacks on AES-MMO and AES-MP and revealed that a differential trail that is not available in the classical setting due to a low ...
详细信息
Recently, Hosoyamada and Sasaki (Eurocrypt'20) proposed dedicated quantum collision attacks on AES-MMO and AES-MP and revealed that a differential trail that is not available in the classical setting due to a low probability can be utilized in the quantum settings. Their works encouraged cryptographers to actively perform security analysis of concrete hash functions in the quantum settings, which had not received much attention before. Xiaoyang Dong et al. (Asiacrypt'20) proposed improved dedicated quantum collision attacks on AES-MMO and AES-MP, and Chauhan et al. (ToSC'21) proposed quantum rebound attacks on the double-block-length hash function Hirose instantiated with 10-round reduced AES-256. In this paper, we propose a quantum collision attack on the Davies-Meyer (DM) hash function instantiated with full-round AES-256. We construct a new chosen-key differential trail for AES-256 based on the trail of Biryukov et al. proposed in 2009 and use it to find collisions of the full AES-256-based DM in a quantum setting. We also present quantum free-start collision attacks on the Hirose and MJH hash functions instantiated with full-round AES-256. These attacks are significant in that they are the first algorithms to find full-round (free-start) collisions. In particular, in the case of Hirose-AES-256, our attacks can cover a larger number of constant c than previously proposed attacks and also cover more rounds.
With the rapid development of quantum computing technology, the traditional cryptosystem will face a significant threat. It is an urgent security issue to study the security impact of quantum computing on classical cr...
详细信息
With the rapid development of quantum computing technology, the traditional cryptosystem will face a significant threat. It is an urgent security issue to study the security impact of quantum computing on classical cryptosystems and provide reliable cryptographic primitives for the post-quantum era. A powerful way to solve this problem is to quantize the classical cryptanalysis tools and use the improved versions for cryptanalysis. In this paper, we propose a quantum Zero-correlation analysis algorithm based on the Bernstein-Vazirani and Grover algorithms. It can find zero-correlation linear hulls for Feistel and SPN structures. We prove the correctness of the algorithm and analyze its complexity. Compared with the classical algorithms, the proposed quantum algorithm has significant advantages when the number of encryption rounds of block ciphers is large. Moreover, compared with the existing quantum Zero-correlation linear analysis, the proposed algorithm is more efficient and does not depend on the algebraic characteristics of the target cipher, which makes the algorithm has more flexible application scenarios. With the development of quantum computers, we discuss the threat of quantum cryptanalysis algorithms to classical security.
quantum computing can provide speedups in solving many problems as the evolution of a quantum system is described by a unitary operator in an exponentially large Hilbert space. Such unitary operators change the phase ...
详细信息
quantum computing can provide speedups in solving many problems as the evolution of a quantum system is described by a unitary operator in an exponentially large Hilbert space. Such unitary operators change the phase of their eigenstates and make quantumalgorithms fundamentally different from their classical counterparts. Based on this unique principle of quantum computing, we develop an algorithmic toolbox, quantum phase processing, that can directly apply arbitrary trigonometric transformations to eigenphases of a unitary operator. The quantum phase processing circuit is constructed simply, consisting of single-qubit rotations and controlled unitaries, typically using only one ancilla qubit. Besides the capability of phase transformation, quantum phase processing in particular can extract the eigeninformation of quantum systems by simply measuring the ancilla qubit, making it naturally compatible with indirect measurement. quantum phase processing complements another powerful framework known as quantum singular value transformation and leads to more intuitive and efficient quantumalgorithms for solving problems that are particularly phase related. As a notable application, we propose a quantum phase estimation algorithm without quantum Fourier transform, which requires the fewest ancilla qubits and matches the best performance so far. We further exploit the power of our method by investigating a plethora of applications in Hamiltonian simulation, entanglement spectroscopy, and quantum entropy estimation, demonstrating improvements or optimality for almost all cases.
Parallel algorithms to accelerate explicitly correlated second-order Moller-Plesset (MP2) and coupled-cluster singles and doubles with perturbative triples [CCSD(T)] calculations and benchmarks on extended molecular s...
Parallel algorithms to accelerate explicitly correlated second-order Moller-Plesset (MP2) and coupled-cluster singles and doubles with perturbative triples [CCSD(T)] calculations and benchmarks on extended molecular systems are reported. A hybrid Open Multi-processing (OpenMP)/Message Passing Interface (MPI) parallel approach is used to distribute the computational load among processor cores and compute nodes. The intermediates at both the MP2 and the CCSD(T) levels are expressed in a density fitting formalism, using only three-index quantities to decrease the amount of data to be stored and communicated. To further reduce compute time, the frozen natural orbital, the natural auxiliary function, and the natural auxiliary basis schemes are implemented in a hybrid parallel manner. The combination of these three approximations and our recent size-consistent explicitly correlated triples correction with the new hybrid parallelization offers a unique accuracy-over-cost performance among explicitly correlated CC methods. Our comprehensive benchmarks demonstrate excellent parallel scaling of the cost-determining operations up to hundreds of processor cores. As demonstrated on the noncovalent interaction energy of the corannulene dimer, highly accurate explicitly correlated CCSD(T) calculations can be carried out for systems of 60 atoms and 2500 orbitals, which were beyond computational limits without local correlation approximations. This enables various applications, such as benchmarking of or, for certain size ranges, replacing local CCSD(T) or density functional methods as well as the further advancement of robust thermochemistry protocols designed for larger molecules of ca. 20-50 atoms.
暂无评论