The complexity of the Quantum Adiabatic Algorithm

The Quantum Adiabatic Algorithm has been proposed as a general purpose algorithm for solving hard optimization problems on a quantum computer. Early work on very small sizes indicated that the running time (complexity) only increased as a (quite small) power of the problem size N. We report results of Quantum Monte Carlo simulations, using parallel tempering, with which we determine the minimum energy gap (and hence get information the complexity) for much bigger sizes than was possible before. The aim is to see if there is a “crossover” to exponential complexity at large N. We present data for the typical (median) complexity as a function of N, which indicate a crossover to a first order transition at large sizes. This implies that the complexity is exponential at large N, at least for the problem studied.     

QSATS: MPI-driven quantum simulations of atomic solids at zero temperature

We describe QSATS, a parallel code for performing variational path integral simulations of the quantum mechanical ground state of monatomic solids. QSATS is designed to treat Boltzmann quantum solids, in which individual atoms are permanently associated with distinguishable crystal lattice sites and undergo large-amplitude zero-point motions around these sites. We demonstrate the capabilities of QSATS by using it to compute the total energy and potential energy of hexagonal close packed solid ⁴He at the density .

Program summary

Program title:QSATSCatalogue identifier: AEJE_v1_0Program summary URL:http://cpc.cs.qub.ac.uk/summaries/AEJE_v1_0.htmlProgram obtainable from: CPC Program Library, Queen?s University, Belfast, N. IrelandLicensing provisions: Standard CPC licence, http://cpc.cs.qub.ac.uk/licence/licence.htmlNo. of lines in distributed program, including test data, etc.: 7329No. of bytes in distributed program, including test data, etc.: 61 685Distribution format: tar.gzProgramming language: Fortran 77.Computer: QSATS should execute on any distributed parallel computing system that has the Message Passing Interface (MPI) [1] libraries installed.Operating system: Unix or Linux.Has the code been vectorized or parallelized?: Yes, parallelized using MPI [1].RAM: The memory requirements of QSATS depend on both the number of atoms in the crystal and the number of replicas in the variational path integral chain. For parameter sets A and C (described in the long write-up), approximately 4.5 Mbytes and 12 Mbytes, respectively, are required for data storage by QSATS (exclusive of the executable code).Classification: 7.7, 16.13.External routines: Message Passing Interface (MPI) [1]Nature of problem: QSATS simulates the quantum mechanical ground state for a monatomic crystal characterized by large-amplitude zero-point motions of individual (distinguishable) atoms around their nominal lattice sites.Solution method: QSATS employs variational path integral quantum Monte Carlo techniques to project the system?s ground state wave function out of a suitably-chosen trial wave function.Restrictions: QSATS neglects quantum statistical effects associated with the exchange of identical particles. As distributed, QSATS assumes that the potential energy function for the crystal is a pairwise additive sum of atom–atom interactions.Additional comments: An auxiliary program, ELOC, is provided that uses the output generated by QSATS to compute both the crystal?s ground state energy and the expectation value of the crystal?s potential energy. End users can modify ELOC as needed to compute the expectation value of other coordinate-space observables.Running time: QSATS requires roughly 3 hours to run a simulation using parameter set A on a cluster of 12 Xeon processors with clock speed 2.8 GHz. Roughly 15 hours are needed to run a simulation using parameter set C on the same cluster.References:

• [1] 

  For information about MPI, visit http://www.mcs.anl.gov/mpi/.

     

Simplicial powers of graphs

In a graph, a vertex is simplicial if its neighborhood is a clique. For an integer k≥1, a graph G=(V_G,E_G) is the k-simplicial power of a graph H=(V_H,E_H) (H a root graph of G) if V_G is the set of all simplicial vertices of H, and for all distinct vertices x and y in V_G, xyE_G if and only if the distance in H between x and y is at most k. This concept generalizes k-leaf powers introduced by Nishimura, Ragde and Thilikos which were motivated by the search for underlying phylogenetic trees; k-leaf powers are the k-simplicial powers of trees. Recently, a lot of work has been done on k-leaf powers and their roots as well as on their variants phylogenetic roots and Steiner roots. For k≤5, k-leaf powers can be recognized in linear time, and for k≤4, structural characterizations are known. For k≥6, the recognition and characterization problems of k-leaf powers are still open. Since trees and block graphs (i.e., connected graphs whose blocks are cliques) have very similar metric properties, it is natural to study k-simplicial powers of block graphs. We show that leaf powers of trees and simplicial powers of block graphs are closely related, and we study simplicial powers of other graph classes containing all trees such as ptolemaic graphs and strongly chordal graphs.     

Monte Carlo simulation of thermodynamic systems with cluster formation under different boundary conditions

Thethermodynamic state function free energy F(T,V,N) as function of the cluster distribution N and the thermodynamic parameters (temperature T and volume V) is calculated in the canonical ensemble. With the help of the Legendre transformation we get all other state functions for different boundary conditions. Monte Carlo simulations with 15000 particles starting from metastable homogeneous initial conditions are made for water and methanol. The Bethe-Weizsäcker ansatz and the Padé approximation are used for the binding energy of clusters. A first-order phase transition is observed under appropriate conditions.     

A simple single layer model to estimate transpiration from vegetation using multi-spectral and meteorological data

A methodology is developed here to model evapotranspiration (λE_c ) from the canopy layer over large areas by combining satellite and ground measurements of biophysical and meteorological variables. The model developed here follows the energy balance approach, where λE_c is estimated as a residual when the net radiation (Rn), sensible heat flux (H) and ground flux (G) are known. Multi-spectral measurements from the NOAA Advanced Very High Resolution Radiometer (AVHRR) were used along with routine meteorological measurements made on the ground to estimate components of the energy balance. The upwelling long wave radiation, and H from the canopy layer were modelled using the canopy temperature, obtained from a linear relation between the Normalized Difference Vegetation Index (NDVI) and surface temperature. This method separates flux measurements from the canopy and bare soil without the need for a complex two layer model. From theoretical analysis of canopy reflectance, leaf area, and canopy resistance, a model is developed to scale the transpiration estimates from the full canopy to give an area averaged estimate from the mean NDVI of the study area. The model was tested using data collected from the First International Satellite Land Surface Climatology Project (ISLSCP) Field Experiment (FIFE), and the results show that the modelled values of total surface evapotranspiration from the soil and canopy layers vary from the ground measurements by less than 9 per cent.     

estimation of mixture complexity for count data

For count data, robust estimation of the number of mixture components in finite mixtures is revisited using L₂ distance. An information criterion based on L₂ distance is shown to yield an estimator, which is also shown to be strongly consistent. Monte Carlo simulations show that our estimator is competitive with other procedures in correctly determining the number of components when the data comes from Poisson mixtures. When the data comes from a negative binomial mixture but the postulated model is a Poisson mixture, simulations show that our estimator is highly competitive with the minimum Hellinger distance (MHD) estimator in terms of robustness against model misspecification. Furthermore, we illustrate the performance of our estimator for a real dataset with overdispersion and zero-inflation. Computational simplicity combined with robustness property makes the L₂E approach an attractive alternative to other procedures in the literature.     

A cubature H∞ filter and its square-root version

In this paper, we present a nonlinear state estimation algorithm based on the fusion of an extended H_∞ (EH_∞F) and a cubature Kalman filter (CKF); the resulting estimator is called a cubature H_∞ filter. The recently developed CKF is a Gaussian approximation of a Bayesian filter and its performance over non-Gaussian noises may degrade. In contrast, the H_∞ filter is capable of estimating the states of linear systems with non-Gaussian noises and the extended H_∞ filter (EH_∞F) can estimate the states of non-linear and non-Gaussian systems. Similar to the H_∞ filter, an EH_∞F also does not make any assumptions about the statistics of the process or measurement noise, but it does require Jacobians during the state estimation of nonlinear systems, which degrade the overall performance when the nonlinearities are severe. The cubature H_∞ filter is developed to have the desirable features of both CKF and EH_∞F. For numerical accuracy, a square-root version of the cubature H_∞ filter is developed using J-unitary transformation. The efficacy of the square-root cubature H_∞ filter is verified on continuous stirred tank reactor and permanent magnet synchronous motor examples.     

Numerical Analysis of Nonlinear Eigenvalue Problems

We provide a priori error estimates for variational approximations of the ground state energy, eigenvalue and eigenvector of nonlinear elliptic eigenvalue problems of the form ?div(A ? u)+Vu+f(u ²)u=λ u, $\|u\|_{L^{2}}=1$ . We focus in particular on the Fourier spectral approximation (for periodic problems) and on the ?₁ and ?₂ finite-element discretizations. Denoting by (u _δ ,λ _δ ) a variational approximation of the ground state eigenpair (u,λ), we are interested in the convergence rates of $\|u_{\delta}-u\|_{H^{1}}$ , $\|u_{\delta}-u\|_{L^{2}}$ , |λ _δ ?λ|, and the ground state energy, when the discretization parameter δ goes to zero. We prove in particular that if A, V and f satisfy certain conditions, |λ _δ ?λ| goes to zero as $\|u_{\delta}-u\|_{H^{1}}^{2}+\|u_{\delta}-u\|_{L^{2}}$ . We also show that under more restrictive assumptions on A, V and f, |λ _δ ?λ| converges to zero as $\|u_{\delta}-u\|_{H^{1}}^{2}$ , thus recovering a standard result for linear elliptic eigenvalue problems. For the latter analysis, we make use of estimates of the error u _δ ?u in negative Sobolev norms.     

The cable trench problem: combining the shortest path and minimum spanning tree problems

Let G=(V,E) be a connected graph with specified vertex v₀∈V, length l(e)⩾0 for each e∈E, and positive parameters τ and γ. The cable-trench problem (CTP) is to find a spanning tree T such that τl_τ(T)+γl_γ(T) is minimized where l_τ(T) is the total length of the spanning tree T and l_γ(T) is the total path length in T from v₀ to all other vertices of V. Since all vertices must be connected to v₀ and only edges from E are allowed, the solution will not be a Steiner tree. Consider the ratio R=τ/γ. For R large enough the solution will be a minimum spanning tree and for R small enough the solution will be a shortest path. In this paper, the CTP will be shown to be NP-complete. A mathematical formulation for the CTP will be provided for specific values of τ and γ. Also, a heuristic will be discussed that will solve the CTP for all values of R.Scope and purposeBoth the shortest path and the minimum spanning tree problems are universally discussed in operations research and management science textbooks. Since the late 1950s, efficient algorithms have been known for both of these problems. In this paper, the cable-trench problem is defined which combines the shortest path problem and the minimum spanning tree problem to create a problem that is shown to be NP-complete. In other words, two easy problems are combined to get a more realistic problem that is difficult to solve. Examples are used to illustrate an efficient and effective heuristic solution procedure for the cable-trench problem.     

An efficient parallel strategy for the two-fixed-endpoint Hamiltonian path problem on distance-hereditary graphs

In this paper, we solve the two-fixed-endpoint Hamiltonian path problem on distance-hereditary graphs efficiently in parallel. Let T_d(|V|,|E|) and P_d(|V|,|E|) denote the parallel time and processor complexities, respectively, required to construct a decomposition tree of a distance-hereditary graph G=(V,E) on a PRAM model M_d. We show that this problem can be solved in O(T_d(|V|,|E|)+log|V|) time using O(P_d(|V|,|E|)+(|V|+|E|)/log|V|) processors on M_d. Moreover, if G is represented by its decomposition tree form, the problem can be solved optimally in O(log|V|) time using O((|V|+|E|)/log|V|) processors on an EREW PRAM. We also obtain a linear-time algorithm which is faster than the previous known O(|V|³) sequential algorithm.     

On edge connectivity of direct products of graphs

Let λ(G) be the edge connectivity of G. The direct product of graphs G and H is the graph with vertex set V(G×H)=V(G)×V(H), where two vertices (u₁,v₁) and (u₂,v₂) are adjacent in G×H if u₁u₂∈E(G) and v₁v₂∈E(H). We prove that λ(G×Kn)=min{n(n−1)λ(G),(n−1)δ(G)} for every nontrivial graph G and n?3. We also prove that for almost every pair of graphs G and H with n vertices and edge probability p, G×H is k-connected, where k=O(²(n/logn)).     

A note on finding all homogeneous set sandwiches

A module is a set of vertices H of a graph G=(V,E) such that each vertex of V?H is either adjacent to all vertices of H or to none of them. A homogeneous set is a nontrivial module. A graph G_s=(V,E_s) is a sandwich for a pair of graphs G_t=(V,E_t) and G=(V,E) if E_t⊆E_s⊆E. In a recent paper, Tang et al. [Inform. Process. Lett. 77 (2001) 17-22] described an O(Δn²) algorithm for testing the existence of a homogeneous set in sandwich graphs of G_t=(V,E_t) and G=(V,E) and then extended it to an enumerative algorithm computing all these possible homogeneous sets. In this paper, we invalidate this latter algorithm by proving there are possibly exponentially many such sets, even if we restrict our attention to strong modules. We then give a correct characterization of a homogeneous set of a sandwich graph.     

Novel hybrid resonant structures and its applications in compact multiband bandpass filters

A novel hybrid resonant structure which can realize compact multiband bandpass filters (BPFs) and its design method are proposed in this article. The hybrid resonant structure is a dual‐plane structure which is an effective combination of a pair of microstrip stepped impedance resonators on the top layer and two nested dual‐mode defected ground structure resonators on the bottom layer. A triband BPF adopting this hybrid resonant structure was presented which was operating at 2.4/5.7 GHz (wireless local area network application) and 3.5 GHz (worldwide interoperability for microwave access application). The size of this filter is only 0.14λ₀ × 0.11λ₀. © 2014 Wiley Periodicals, Inc. Int J RF and Microwave CAE 24:690–696, 2014.     

Note on the Homogeneous Set Sandwich Problem

A homogeneous set is a non-trivial module of a graph, i.e., a non-unitary, proper subset H of a graph's vertices such that all vertices in H have the same neighbors outside H. Given two graphs G₁(V,E₁), G₂(V,E₂), the Homogeneous Set Sandwich Problem asks whether there exists a sandwich graph GS(V,ES), E₁⊆ES⊆E₂, which has a homogeneous set. Recently, Tang et al. [Inform. Process. Lett. 77 (2001) 17-22] proposed an interesting O(_?1⋅n²) algorithm for this problem, which has been considered its most efficient algorithm since. We show the incorrectness of their algorithm by presenting three counterexamples.     

Error measures for fuzzy linear regression: Monte Carlo simulation approach

The focus of this study is to use Monte Carlo method in fuzzy linear regression. The purpose of the study is to figure out the appropriate error measures for the estimation of fuzzy linear regression model parameters with Monte Carlo method. Since model parameters are estimated without any mathematical programming or heavy fuzzy arithmetic operations in fuzzy linear regression with Monte Carlo method. In the literature, only two error measures (E₁ and E₂) are available for the estimation of fuzzy linear regression model parameters. Additionally, accuracy of available error measures under the Monte Carlo procedure has not been evaluated. In this article, mean square error, mean percentage error, mean absolute percentage error, and symmetric mean absolute percentage error are proposed for the estimation of fuzzy linear regression model parameters with Monte Carlo method. Moreover, estimation accuracies of existing and proposed error measures are explored. Error measures are compared to each other in terms of estimation accuracy; hence, this study demonstrates that the best error measures to estimate fuzzy linear regression model parameters with Monte Carlo method are proved to be E₁, E₂, and the mean square error. One the other hand, the worst one can be given as the mean percentage error. These results would be useful to enrich the studies that have already focused on fuzzy linear regression models.     

On Bounded Leg Shortest Paths Problems

Let V be a set of points in a d-dimensional l _p -metric space. Let s,t∈V and let L be a real number. An L-bounded leg path from s to t is an ordered set of points which connects s to t such that the leg between any two consecutive points in the set has length of at most L. The minimal path among all these paths is the L-bounded leg shortest path from s to t. In the s–t Bounded Leg Shortest Path (stBLSP) problem we are given two points s and t and a real number L, and are required to compute an L-bounded leg shortest path from s to t. In the All-Pairs Bounded Leg Shortest Path (apBLSP) problem we are required to build a data structure that, given any two query points from V and a real number L, outputs the length of the L-bounded leg shortest path (a distance query) or the path itself (a path query). In this paper we obtain the following results:     

Design of a subarray with special radiation pattern for low profile wide‐angle scanning phased array

A low profile subarray with a special radiation pattern for the wide‐angle H‐plane scanning phased array is presented. Five parallel dipoles located above a metal ground serve as the radiator. The differential evolution (DE) algorithm is used to obtain the weights for a special radiation pattern, which is realized by a corresponding feed network. The overall dimension of the proposed subarray is only 0.55λ₀ × 0.55λ₀ × 0.14λ₀. The prototype is fabricated and measured, and the measurement results are consistent with the simulation results. Because of the special radiation pattern and compact size, this subarray is suitable as an element in the wide‐angle scanning phased array. A uniform linear array consisting of five proposed subarrays is built in high frequency structural simulator, and the simulated results show that the main beam can scan nearly from ?70° to +70° in the H‐plane with a gain fluctuation less than 3 dB.     

量子退火算法研究进展

在数学和应用领域,量子退火算法是一类新的量子优化算法.不同于经典模拟退火算法利用热波动来搜寻问题的最优解,量子退火算法利用量子波动产生的量子隧穿效应来使算法摆脱局部最优,而实现全局优化.在已有的研究中,量子退火算法在某些问题上展现出良好的优化效果.系统地综述了量子退火算法的基本原理和近年来的主要研究进展,较为详细地介绍了几个主要的量子退火算法,对量子退火算法的优点和可能的不足进行了分析评述,并对今后的研究方向进行了展望.     

Fast Algorithm for Computing the Upper Endpoint of Sample Variance for Interval Data: Case of Sufficiently Accurate Measurements

When we have n results x₁,...,x_n of repeated measurement of the same quantity, the traditional statistical approach usually starts with computing their sample average E and their sample variance V. Often, due to the inevitable measurement uncertainty, we do not know the exact values of the quantities, we only know the intervals x_i of possible values of x₁ In such situations, for different possible values x_i∈ x_i, we get different values of the variance. We must therefore find the range V of possible values of V. It is known that in general, this problem is NP-hard. For the case when the measurements are sufficiently accurate (in some precise sense), it is known that we can compute the interval V in quadratic time O(n²). In this paper, we describe a new algorithm for computing V that requires time O(n log(n)) (which is much faster than O(n²)).