A data lake(DL),abbreviated as DL,denotes a vast reservoir or repository of data.It accumulates substantial volumes of data and employs advanced analytics to correlate data from diverse origins containing various form...A data lake(DL),abbreviated as DL,denotes a vast reservoir or repository of data.It accumulates substantial volumes of data and employs advanced analytics to correlate data from diverse origins containing various forms of semi-structured,structured,and unstructured information.These systems use a flat architecture and run different types of data analytics.NoSQL databases are nontabular and store data in a different manner than the relational table.NoSQL databases come in various forms,including key-value pairs,documents,wide columns,and graphs,each based on its data model.They offer simpler scalability and generally outperform traditional relational databases.While NoSQL databases can store diverse data types,they lack full support for atomicity,consistency,isolation,and durability features found in relational databases.Consequently,employing machine learning approaches becomes necessary to categorize complex structured query language(SQL)queries.Results indicate that the most frequently used automatic classification technique in processing SQL queries on NoSQL databases is machine learning-based classification.Overall,this study provides an overview of the automatic classification techniques used in processing SQL queries on NoSQL databases.Understanding these techniques can aid in the development of effective and efficient NoSQL database applications.展开更多
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 ...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.展开更多
Performance predictions for database queries allow service providers to determine what resources are needed to ensure their performance. Cost-based or rule-based approaches have been proposed to optimize database quer...Performance predictions for database queries allow service providers to determine what resources are needed to ensure their performance. Cost-based or rule-based approaches have been proposed to optimize database query execution plans. However, Virtual Machine （VM）-based database services have little or no sharing of resources or interactions between applications hosted on shared infrastructures. Neither providers nor users have the right combination of visibility/access/expertise to perform proper tuning and provisioning. This paper presents a performance prediction model for query execution time estimates based on the query complexity for various data sizes. The user query execution time is a combination of five basic operator complexities： O（1）, O（log（n））, O（n）, O（nlog（n））, and O（n2）. Moreover, tests indicate that not all queries are equally important for performance prediction. As such, this paper illustrates a performance-sensitive query locating process on three benchmarks： RUBiS, RUBBoS, and TPC-W. A key observation is that performance-sensitive queries are only a small proportion （20%） of the application query set. Evaluation of the performance model on the TPC-W benchmark shows that the query complexity in a real life scenario has an average prediction error rate of less than 10% which demonstrates the effectiveness of this predictive model.展开更多
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 att...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.展开更多
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 ...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.展开更多
Correlation functions are often employed to quantify the relationships among interdependent variables or sets of data.Recently,a new class of correlation functions,called FORRELATION,has been introduced by Aaronson an...Correlation functions are often employed to quantify the relationships among interdependent variables or sets of data.Recently,a new class of correlation functions,called FORRELATION,has been introduced by Aaronson and Ambainis for studying the query complexity of quantum devices.It was found that there exists a quantum query algorithm solving 2-fold FORRELATION problems with an exponential quantum speedup over all possible classical means,which represents essentially the largest possible separation between quantum and classical query complexities.Here we report an experimental study probing the2-fold and 3-fold FORRELATIONS encoded in nuclear spins.The major experimental challenge is to control the spin fluctuation to within a threshold value,which is achieved by developing a set of optimized GRAPE pulse sequences.Overall,our small-scale implementation indicates that the quantum query algorithm is capable of determining the values of FORRELATIONS within an acceptable accuracy required for demonstrating quantum supremacy,given the current technology and in the presence of experimental noise.展开更多
基金supported by the Student Scheme provided by Universiti Kebangsaan Malaysia with the Code TAP-20558.
文摘A data lake(DL),abbreviated as DL,denotes a vast reservoir or repository of data.It accumulates substantial volumes of data and employs advanced analytics to correlate data from diverse origins containing various forms of semi-structured,structured,and unstructured information.These systems use a flat architecture and run different types of data analytics.NoSQL databases are nontabular and store data in a different manner than the relational table.NoSQL databases come in various forms,including key-value pairs,documents,wide columns,and graphs,each based on its data model.They offer simpler scalability and generally outperform traditional relational databases.While NoSQL databases can store diverse data types,they lack full support for atomicity,consistency,isolation,and durability features found in relational databases.Consequently,employing machine learning approaches becomes necessary to categorize complex structured query language(SQL)queries.Results indicate that the most frequently used automatic classification technique in processing SQL queries on NoSQL databases is machine learning-based classification.Overall,this study provides an overview of the automatic classification techniques used in processing SQL queries on NoSQL databases.Understanding these techniques can aid in the development of effective and efficient NoSQL database applications.
基金4 Acknowledgements The author would like to thank G.L. Long for very helpful discussion, and thank J.Q. Yi for his generous help in plotting the function figures.
文摘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.
文摘Performance predictions for database queries allow service providers to determine what resources are needed to ensure their performance. Cost-based or rule-based approaches have been proposed to optimize database query execution plans. However, Virtual Machine （VM）-based database services have little or no sharing of resources or interactions between applications hosted on shared infrastructures. Neither providers nor users have the right combination of visibility/access/expertise to perform proper tuning and provisioning. This paper presents a performance prediction model for query execution time estimates based on the query complexity for various data sizes. The user query execution time is a combination of five basic operator complexities： O（1）, O（log（n））, O（n）, O（nlog（n））, and O（n2）. Moreover, tests indicate that not all queries are equally important for performance prediction. As such, this paper illustrates a performance-sensitive query locating process on three benchmarks： RUBiS, RUBBoS, and TPC-W. A key observation is that performance-sensitive queries are only a small proportion （20%） of the application query set. Evaluation of the performance model on the TPC-W benchmark shows that the query complexity in a real life scenario has an average prediction error rate of less than 10% which demonstrates the effectiveness of this predictive model.
基金National Natural Science Foundation of China(Grant Nos.62272492,61772565)Guangdong Basic and Applied Basic Research Foundation(No.2020B1515020050).
文摘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.
基金supported by the National Natural Science Foundation of China under Grant Nos.61772565 and 62272492the Guangdong Basic and Applied Basic Research Foundation under Grant No.2020B1515020050the Key Research and Development Program of Guangdong Province of China under Grant No.2018B030325001.
文摘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.
基金supported by the National Natural Science Foundation of China(11175094,91221205,and 11405093)the National Basic Research Program of China(2015CB921002)
文摘Correlation functions are often employed to quantify the relationships among interdependent variables or sets of data.Recently,a new class of correlation functions,called FORRELATION,has been introduced by Aaronson and Ambainis for studying the query complexity of quantum devices.It was found that there exists a quantum query algorithm solving 2-fold FORRELATION problems with an exponential quantum speedup over all possible classical means,which represents essentially the largest possible separation between quantum and classical query complexities.Here we report an experimental study probing the2-fold and 3-fold FORRELATIONS encoded in nuclear spins.The major experimental challenge is to control the spin fluctuation to within a threshold value,which is achieved by developing a set of optimized GRAPE pulse sequences.Overall,our small-scale implementation indicates that the quantum query algorithm is capable of determining the values of FORRELATIONS within an acceptable accuracy required for demonstrating quantum supremacy,given the current technology and in the presence of experimental noise.
