Quantum Query Complexity for Searching Multiple Marked States from an Unsorted Database

An important and usual sort of search problems is to find all marked states from an unsorted database with a large number of states. Grover＇s original quantum search algorithm is for finding single marked state with uncertainty, and it has been generalized to the case of multiple marked states, as well as been modified to find single marked state with certainty. However, the query complexity for finding all multiple marked states has not been addressed. We use a generalized Long＇s algorithm with high precision to solve such a problem. We calculate the approximate query complexity, which increases with the number of marked states and with the precision that we demand. In the end we introduce an algorithm for the problem on a ＂duality computer＂ and show its advantage over other algorithms.

Quantum Chemistry Based Computational Study on the Conformational Population of a Neodymium Neodecanoate Complex

The title complex is widely used as an efficient key component of Ziegler-Natta catalyst for stereospecific polymerization of dienes to produce synthetic rubbers. However, the quantitative structure-activity relationship（QSAR） of this kind of complexes is still not clear mainly due to the difficulties to obtain their geometric molecular structures through laboratory experiments. An alternative solution is the quantum chemistry calculation in which the comformational population shall be determined. In this study, ten conformers of the title complex were obtained with the function of molecular dynamics conformational search in Gabedit 2.4.8, and their geometry optimization and thermodynamics calculation were made with a Sparkle/PM7 approach in MOPAC 2012. Their Gibbs free energies at 1 atm. and 298.15 K were calculated. Population of the conformers was further calculated out according to the theory of Boltzmann distribution, indicating that one of the ten conformers has a dominant population of 77.13%.

Quantum Circuit Complexity as a Physical Observable

This work proposes quantum circuit complexity—the minimal number of elementary operations needed to implement a quantum transformation—be established as a legitimate physical observable. We prove that circuit complexity satisfies all requirements for physical observables, including self-adjointness, gauge invariance, and a consistent measurement theory with well-defined uncertainty relations. We develop complete protocols for measuring complexity in quantum systems and demonstrate its connections to gauge theory and quantum gravity. Our results suggest that computational requirements may constitute physical laws as fundamental as energy conservation. This framework grants insights into the relationship between quantum information, gravity, and the emergence of spacetime geometry while offering practical methods for experimental verification. Our results indicate that the physical universe may be governed by both energetic and computational constraints, with profound implications for our understanding of fundamental physics.

Impact of Informatics on QIPC

Quantum information processing and communication(QIPC) is an area of science that has two main goals: On one side,it tries to explore(still not well known) potential of quantum phenomena for(efficient and reliable) information processing and(efficient,reliable and secure) communication.On the other side,it tries to use quantum information storing,processing and transmitting paradigms,principles,laws,limitations,concepts,models and tools to get deeper insights into the phenomena of quantum world and to find efficient ways to describe and handle/simulate various complex physical phenomena.In order to do that QIPC has to use concepts,models,theories,methods and tools of both physics and informatics.The main role of physics at that is to discover primitive physical phenomena that can be used to design and maintain complex and reliable information storing,processing and transmitting systems.The main role of informatics is,one one side,to explore,from the information processing and communication point of view,limitations and potentials of the potential quantum information processing and communication technology,and to prepare information processing methods that could utilise potential of quantum information processing and communication technologies.On the other side,the main role of informatics is to guide and support,by theoretical tools and outcomes,physics oriented research in QIPC.The paper is to describe and analyse a variety of ways and potential informatics contributes and should/could contribute to the development of QIPC--see also Gruska(1999,2006,2008).

Quantum speedup and limitations on matroid property problems

Matroid theory has been developed to be a mature branch of mathematics and has extensive applications in combinatorial optimization,algorithm design and so on.On the other hand,quantum computing has attracted much attention and has been shown to surpass classical computing on solving some computational problems.Surprisingly,crossover studies of the two fields seem to be missing in the literature.This paper initiates the study of quantum algorithms for matroid property problems.It is shown that quadratic quantum speedup is possible for the calculation problem of finding the girth or the number of circuits(bases,flats,hyperplanes)of a matroid,and for the decision problem of deciding whether a matroid is uniform or Eulerian,by giving a uniform lower boundΩ■on the query complexity of all these problems.On the other hand,for the uniform matroid decision problem,an asymptotically optimal quantum algorithm is proposed which achieves the lower bound,and for the girth problem,an almost optimal quantum algorithm is given with query complexityO■.In addition,for the paving matroid decision problem,a lower boundΩ■on the query complexity is obtained,and an O■ quantum algorithm is presented.

Complex duality quantum computers acting on pure and mixed states

The aim of this paper is to establish a mathematical fundamental of complex duality quantum computers(CDQCs) acting on vector-states(pure states) and operator-states(mixed states),respectively.A CDQC consists of a complex divider,a group of quantum gates represented by unitary operators,or quantum operations represented by completely positive and trace-preserving mappings,and a complex combiner.It is proved that the divider and the combiner of a CDQC are an isometry and a contraction,respectively.It is proved that the divider and the combiner of a CDQC acting on vector-states are dual,and in the finite dimensional case,it is proved that the divider and the combiner of a CDQC acting on operator-states(matrix-states) are also dual.Lastly,the loss of an input state passing through a CDQC is measured.

On a class of quantum Turing machine halting deterministically

We consider a subclass of quantum Turing machines (QTM), named stationary rotational quantum Turing machine (SR-QTM), which halts deterministically and has deterministic tape head position. A quantum state transition diagram (QSTD) is proposed to describe SR-QTM. With QSTD, we construct a SR-QTM which is universal for all near-trivial transformations. This indicates there exists a QTM which is universal for the above subclass. Finally we show that SR-QTM is computational equivalent with ordinary QTM in the bounded error setting. It can be seen that SR-QTMs have deterministic tape head position and halt deterministically, and thus the halting scheme problem will not exist for this class of QTMs.

Characterization of Exact One-Query Quantum Algorithms for Partial Boolean Functions

The query model(or black-box model)has attracted much attention from the communities of both classical and quantum computing.Usually,quantum advantages are revealed by presenting a quantum algorithm that has a better query complexity than its classical counterpart.In the history of quantum algorithms,the Deutsch algorithm and the Deutsch-Jozsa algorithm play a fundamental role and both are exact one-query quantum algorithms.This leads us to con-sider the problem:what functions can be computed by exact one-query quantum algorithms?This problem has been ad-dressed in the literature for total Boolean functions and symmetric partial Boolean functions,but is still open for general partial Boolean functions.Thus,in this paper,we continue to characterize the computational power of exact one-query quantum algorithms for general partial Boolean functions.First,we present several necessary and sufficient conditions for a partial Boolean function to be computed by exact one-query quantum algorithms.Second,inspired by these conditions,we discover some new representative functions that can be computed by exact one-query quantum algorithms but have an essential difference from the already known ones.Specially,it is worth pointing out that before our work,the known func-tions that can be computed by exact one-query quantum algorithms are all symmetric functions and the quantum algo-rithm used is essentially the Deutsch-Jozsa algorithm,whereas the functions discovered in this paper are generally asym-metric and new algorithms to compute these functions are required.Thus,this expands the class of functions that can be computed by exact one-query quantum algorithms.