Adiabatic quantum optimization with qudits

Most realistic solid state devices considered as qubits are not true two-state systems. If the energy separation of the upper energy levels from the lowest two levels is not large, then these upper states may affect the evolution of the ground state over time and therefore cannot be neglected. In this work, we study the effect of energy levels beyond the lowest two energy levels on adiabatic quantum optimization in a device with a double-well potential as the basic logical element. We show that the extra levels can be modeled by adding additional ancilla qubits coupled to the original logical qubits, and that the presence of upper levels has no effect on the final ground state. We also study the influence of upper energy levels on the minimum gap for a set of 8-qubit spin glass instances.     

A comparison of approaches for finding minimum identifying codes on graphs

In order to formulate mathematical conjectures likely to be true, a number of base cases must be determined. However, many combinatorial problems are NP-hard and the computational complexity makes this research approach difficult using a standard brute force approach on a typical computer. One sample problem explored is that of finding a minimum identifying code. To work around the computational issues, a variety of methods are explored and consist of a parallel computing approach using MATLAB, an adiabatic quantum optimization approach using a D-Wave quantum annealing processor, and lastly using satisfiability modulo theory (SMT) and corresponding SMT solvers. Each of these methods requires the problem to be formulated in a unique manner. In this paper, we address the challenges of computing solutions to this NP-hard problem with respect to each of these methods.     

Benchmarking optimization solvers for structural topology optimization

The purpose of this article is to benchmark different optimization solvers when applied to various finite element based structural topology optimization problems. An extensive and representative library of minimum compliance, minimum volume, and mechanism design problem instances for different sizes is developed for this benchmarking. The problems are based on a material interpolation scheme combined with a density filter. Different optimization solvers including Optimality Criteria (OC), the Method of Moving Asymptotes (MMA) and its globally convergent version GCMMA, the interior point solvers in IPOPT and FMINCON, and the sequential quadratic programming method in SNOPT, are benchmarked on the library using performance profiles. Whenever possible the methods are applied to both the nested and the Simultaneous Analysis and Design (SAND) formulations of the problem. The performance profiles conclude that general solvers are as efficient and reliable as classical structural topology optimization solvers. Moreover, the use of the exact Hessians in SAND formulations, generally produce designs with better objective function values. However, with the benchmarked implementations solving SAND formulations consumes more computational time than solving the corresponding nested formulations.     

Fast Nonlinear Least Squares Optimization of Large-Scale Semi-Sparse Problems

Many problems in computer graphics and vision can be formulated as a nonlinear least squares optimization problem, for which numerous off-the-shelf solvers are readily available. Depending on the structure of the problem, however, existing solvers may be more or less suitable, and in some cases the solution comes at the cost of lengthy convergence times. One such case is semi-sparse optimization problems, emerging for example in localized facial performance reconstruction, where the nonlinear least squares problem can be composed of hundreds of thousands of cost functions, each one involving many of the optimization parameters. While such problems can be solved with existing solvers, the computation time can severely hinder the applicability of these methods. We introduce a novel iterative solver for nonlinear least squares optimization of large-scale semi-sparse problems. We use the nonlinear Levenberg-Marquardt method to locally linearize the problem in parallel, based on its first-order approximation. Then, we decompose the linear problem in small blocks, using the local Schur complement, leading to a more compact linear system without loss of information. The resulting system is dense but its size is small enough to be solved using a parallel direct method in a short amount of time. The main benefit we get by using such an approach is that the overall optimization process is entirely parallel and scalable, making it suitable to be mapped onto graphics hardware (GPU). By using our minimizer, results are obtained up to one order of magnitude faster than other existing solvers, without sacrificing the generality and the accuracy of the model. We provide a detailed analysis of our approach and validate our results with the application of performance-based facial capture using a recently-proposed anatomical local face deformation model.     

Job scheduling and processor allocation for grid computing on metacomputers

Scheduling is a fundamental issue in achieving high performance on metacomputers and computational grids. For the first time, the job scheduling problem for grid computing on metacomputers is studied as a combinatorial optimization problem. A cost model is proposed for modeling communication heterogeneity on computational grids. A processor allocation algorithm is developed which always finds an optimal processor allocation that minimizes the effective execution time of a job when the job is being scheduled. It is proven that the list scheduling (LS) algorithm can achieve reasonable worst-case performance bound in grid environments supporting distributed supercomputing with large applications. We compare the performance of various job scheduling and processor allocation algorithms for grid computing on metacomputers. We evaluate the performance of 128 combinations of two job scheduling algorithms, four initial job ordering strategies, four processor allocation algorithms, and four metacomputers by extensive simulation. It is found that the combination of largest job first (LJF) initial job ordering and minimum effective execution time (MEET) or largest machine first (LMF) processor allocation algorithm yields the best average-case performance, and the choice of FCFS and LS depends on the range of job sizes. It is also observed that communication heterogeneity does have significant impact on schedule lengths.     

Solving the multi-stage portfolio optimization problem with a novel particle swarm optimization

Solving the multi-stage portfolio optimization (MSPO) problem is very challenging due to nonlinearity of the problem and its high consumption of computational time. Many heuristic methods have been employed to tackle the problem. In this paper, we propose a novel variant of particle swarm optimization (PSO), called drift particle swarm optimization (DPSO), and apply it to the MSPO problem solving. The classical return-variance function is employed as the objective function, and experiments on the problems with different numbers of stages are conducted by using sample data from various stocks in S&P 100 index. We compare performance and effectiveness of DPSO, particle swarm optimization (PSO), genetic algorithm (GA) and two classical optimization solvers (LOQO and CPLEX), in terms of efficient frontiers, fitness values, convergence rates and computational time consumption. The experiment results show that DPSO is more efficient and effective in MSPO problem solving than other tested optimization tools.     

绝热量子优化算法研究进展

绝热量子优化计算于2001年首次提出,它基于绝热量子演化研究NPC组合优化问题,是量子计算的领域热点。主要回顾了绝热量子优化算法研究领域所取得的进展,阐述绝热量子优化算法研究所采用的主要方法和关键技术,最后分析绝热量子优化计算的发展趋势。     

An efficient second-order SQP method for structural topology optimization

This article presents a Sequential Quadratic Programming (SQP) solver for structural topology optimization problems named TopSQP. The implementation is based on the general SQP method proposed in Morales et al. J Numer Anal 32(2):553–579 (2010) called SQP+. The topology optimization problem is modelled using a density approach and thus, is classified as a nonconvex problem. More specifically, the SQP method is designed for the classical minimum compliance problem with a constraint on the volume of the structure. The sub-problems are defined using second-order information. They are reformulated using the specific mathematical properties of the problem to significantly improve the efficiency of the solver. The performance of the TopSQP solver is compared to the special-purpose structural optimization method, the Globally Convergent Method of Moving Asymptotes (GCMMA) and the two general nonlinear solvers IPOPT and SNOPT. Numerical experiments on a large set of benchmark problems show good performance of TopSQP in terms of number of function evaluations. In addition, the use of second-order information helps to decrease the objective function value.     

Quantum adiabatic machine learning

We develop an approach to machine learning and anomaly detection via quantum adiabatic evolution. This approach consists of two quantum phases, with some amount of classical preprocessing to set up the quantum problems. In the training phase we identify an optimal set of weak classifiers, to form a single strong classifier. In the testing phase we adiabatically evolve one or more strong classifiers on a superposition of inputs in order to find certain anomalous elements in the classification space. Both the training and testing phases are executed via quantum adiabatic evolution. All quantum processing is strictly limited to two-qubit interactions so as to ensure physical feasibility. We apply and illustrate this approach in detail to the problem of software verification and validation, with a specific example of the learning phase applied to a problem of interest in flight control systems. Beyond this example, the algorithm can be used to attack a broad class of anomaly detection problems.     

Efficient quantum inspired meta-heuristics for multi-level true colour image thresholding

Thresholding is a commonly used simple and effective technique for image segmentation. The computational time in multi-level thresholding significantly increases with the level of computation because of exhaustive searching, adding to exponential growth of computational complexity. Hence, in this paper, the features of quantum computing are exploited to introduce four different quantum inspired meta-heuristic techniques to accelerate the execution of multi-level thresholding. The proposed techniques are Quantum Inspired Genetic Algorithm, Quantum Inspired Simulated Annealing, Quantum Inspired Differential Evolution and Quantum Inspired Particle Swarm Optimization. The effectiveness of the proposed techniques is exhibited in comparison with the backtracking search optimization algorithm, the composite DE method, the classical genetic algorithm, the classical simulated annealing, the classical differential evolution and the classical particle swarm optimization for ten real life true colour images. The experimental results are presented in terms of optimal threshold values for each primary colour component, the fitness value and the computational time (in seconds) at different levels. Thereafter, the quality of thresholding is judged in terms of the peak signal-to-noise ratio for each technique. Moreover, statistical test, referred to as Friedman test, and also median based estimation among all techniques, are conducted separately to judge the preeminence of a technique among them. Finally, the performance of each technique is visually judged from convergence plots for all test images, which affirms that the proposed quantum inspired particle swarm optimization technique outperforms other techniques.     

Room-temperature spin-photon interface for quantum networks

Although remarkable progress has been achieved recently, to construct an optical cavity where a nitrogen-vacancy (NV) colour centre in diamond is coupled to an optical field in the strong coupling regime is rather difficult. We propose an architecture for a scalable quantum interface capable of interconverting photonic and NV spin qubits, which can work well without the strong coupling requirement. The dynamics of the interface applies an adiabatic passage to sufficiently reduce the decoherence from an excited state of a NV colour centre in diamond. This quantum interface can accomplish many quantum network operations like state transfer and entanglement distribution between qubits at distant nodes. Exact numerical simulations show that high-fidelity quantum interface operations can be achieved under room-temperature and realistic experimental conditions.     

Optimal control of multi-level quantum system with energy cost functional

In this paper we have synthesized optimal control of multi-level quantum system by representing unitary operator in terms of the projection operators of the Hamiltonian of the system. We have solved the steering problem for multi-level quantum systems minimizing energy cost functional of the control. The optimal control problem of the time evolution of quantum spin of Pauli two-level system subjected to an external field with the minimum energy function is also illustrated and formulated in terms of the quantum spin up and spin down states of the Pauli two-level system.     

On the Hitting Times of Quantum Versus Random Walks

The hitting time of a classical random walk (Markov chain) is the time required to detect the presence of—or equivalently, to find—a marked state. The hitting time of a quantum walk is subtler to define; in particular, it is unknown whether the detection and finding problems have the same time complexity. In this paper we define new Monte Carlo type classical and quantum hitting times, and we prove several relationships among these and the already existing Las Vegas type definitions. In particular, we show that for some marked state the two types of hitting time are of the same order in both the classical and the quantum case. Then, we present new quantum algorithms for the detection and finding problems. The complexities of both algorithms are related to the new, potentially smaller, quantum hitting times. The detection algorithm is based on phase estimation and is particularly simple. The finding algorithm combines a similar phase estimation based procedure with ideas of Tulsi from his recent theorem (Tulsi A.: Phys. Rev. A 78:012310 2008) for the 2D grid. Extending his result, we show that we can find a unique marked element with constant probability and with the same complexity as detection for a large class of quantum walks—the quantum analogue of state-transitive reversible ergodic Markov chains. Further, we prove that for any reversible ergodic Markov chain P, the quantum hitting time of the quantum analogue of P has the same order as the square root of the classical hitting time of P. We also investigate the (im)possibility of achieving a gap greater than quadratic using an alternative quantum walk. In doing so, we define a notion of reversibility for a broad class of quantum walks and show how to derive from any such quantum walk a classical analogue. For the special case of quantum walks built on reflections, we show that the hitting time of the classical analogue is exactly the square of the quantum walk.     

The Performance Analysis of a Quantum Brayton Refrigeration Cycle with an Ideal Bose Gas

A Brayton refrigeration cycle using an ideal Bose gas as the working substance is simply referred to as a quantum Brayton refrigeration cycle, which consists of two constant-pressure and two adiabatic processes. The influence of quantum degeneracy on the performance of the cycle is investigated, based on the correction equation of state of an ideal Bose gas. The general expressions of the coefficient of performance, refrigeration load and work input of the cycle are calculated. The lowest temperature of the working substance and the minimum pressure ratio of the two constant-pressure processes for a quantum Brayton refrigeration cycle are determined. The variations of the relative refrigeration load with the temperature of the cooled space and the pressure of the low constant-pressure process are discussed for three special cases. Some curves related to the important performance parameters are given. The results obtained here are compared with those of a classical Brayton refrigeration cycle using an ideal gas as the working substance. Some significant conclusions are obtained.     

Efficient benchmarking of algorithm configurators via model-based surrogates

The optimization of algorithm (hyper-)parameters is crucial for achieving peak performance across a wide range of domains, ranging from deep neural networks to solvers for hard combinatorial problems. However, the proper evaluation of new algorithm configuration (AC) procedures (or configurators) is hindered by two key hurdles. First, AC scenarios are hard to set up, including the target algorithm to be optimized and the problem instances to be solved. Second, and even more significantly, they are computationally expensive: a single configurator run involves many costly runs of the target algorithm. Here, we propose a benchmarking approach that uses surrogate scenarios, which are computationally cheap while remaining close to the original AC scenarios. These surrogate scenarios approximate the response surface corresponding to true target algorithm performance using a regression model. In our experiments, we construct and evaluate surrogate scenarios for hyperparameter optimization as well as for AC problems that involve performance optimization of solvers for hard combinatorial problems. We generalize previous work by building surrogates for AC scenarios with multiple problem instances, stochastic target algorithms and censored running time observations. We show that our surrogate scenarios capture overall important characteristics of the original AC scenarios from which they were derived, while being much easier to use and orders of magnitude cheaper to evaluate.     

Shape reanalysis and sensitivities utilizing preconditioned iterative boundary solvers

The computational advantages associated with the utilization of preconditioned iterative equation solvers are quantified for the reanalysis of perturbed shapes using continuum structural boundary element analysis (BEA). Both single- and multizone three-dimensional problems are examined. Significant redutions in computer time are obtained by making use of previously computed solution vectors and preconditioners in subsequent analyses. The effectiveness of this technique is demonstrated for the computation of shape response sensitivities required in shape optimization. Computer times and accuracies achieved using the preconditioned iterative solvers are compared with those obtained via direct solvers and implicit differentiation of the boundary integral equations. It is concluded that this approach employing preconditioned iterative equation solvers in reanalysis and sensitivity analysis can be competitive with if not superior to those involving direct solvers.     

Parallel framework for topology optimization using the method of moving asymptotes

The complexity of problems attacked in topology optimization has increased dramatically during the past decade. Examples include fully coupled multiphysics problems in thermo-elasticity, fluid-structure interaction, Micro-Electro Mechanical System (MEMS) design and large-scale three dimensional problems. The only feasible way to obtain a solution within a reasonable amount of time is to use parallel computations in order to speed up the solution process. The focus of this article is on a fully parallel topology optimization framework implemented in C++, with emphasis on utilizing well tested and simple to implement linear solvers and optimization algorithms. However, to ensure generality, the code is developed to be easily extendable in terms of physical models as well as in terms of solution methods, without compromising the parallel scalability. The widely used Method of Moving Asymptotes optimization algorithm is parallelized and included as a fundamental part of the code. The capabilities of the presented approaches are demonstrated on topology optimization of a Stokes flow problem with target outflow constraints as well as the minimum compliance problem with a volume constraint from linear elasticity.     

Workflow of the Grover algorithm simulation incorporating CUDA and GPGPU

The Grover quantum search algorithm, one of only a few representative quantum algorithms, can speed up many classical algorithms that use search heuristics. No true quantum computer has yet been developed. For the present, simulation is one effective means of verifying the search algorithm. In this work, we focus on the simulation workflow using a compute unified device architecture (CUDA). Two simulation workflow schemes are proposed. These schemes combine the characteristics of the Grover algorithm and the parallelism of general-purpose computing on graphics processing units (GPGPU). We also analyzed the optimization of memory space and memory access from this perspective. We implemented four programs on CUDA to evaluate the performance of schemes and optimization. Through experimentation, we analyzed the organization of threads suited to Grover algorithm simulations, compared the storage costs of the four programs, and validated the effectiveness of optimization. Experimental results also showed that the distinguished program on CUDA outperformed the serial program of libquantum on a CPU with a speedup of up to 23 times (12 times on average), depending on the scale of the simulation.     

Robustness measure of hybrid intra-particle entanglement,discord, and classical correlation with initial Werner state

Quantum information processing is largely dependent on the robustness of non-classical correlations, such as entanglement and quantum discord. However, all the realistic quantum systems are thermodynamically open and lose their coherence with time through environmental interaction. The time evolution of quantum entanglement, discord, and the respective classical correlation for a single, spin-1/2 particle under spin and energy degrees of freedom, with an initial Werner state, has been investigated in the present study. The present intra-particle system is considered to be easier to produce than its inter-particle counterpart. Experimentally, this type of system may be realized in the well-known Penning trap. The most stable correlation was identified through maximization of a system-specific global objective function. Quantum discord was found to be the most stable, followed by the classical correlation. Moreover, all the correlations were observed to attain highest robustness under initial Bell state, with minimum possible dephasing and decoherence parameters.     

一种新型的多目标优化混合量子进化算法

针对复杂多目标优化问题,提出一种混合量子进化算法,并利用它求解多目标函数优化问题。该算法根据多目标优化的特点,创建外部集合保存历代搜索到的非支配解,利用其中的精英个体设计了一种旋转角自适应调整的量子门更新策略,并对量子比特表示的概率幅设置最大和最小阈值,以防止量子群体早熟收敛。借鉴量子门引入了专门针对量子个体的旋转交叉算子,同时小概率地对量子比特进行取反变异操作。对所提算法的计算复杂度进行了理论分析。与另一种已有的多目标量子进化算法的比较结果表明,所提算法具有更好的收敛性能、分布特性及求解效率。