The analytical Scheme calculator for angular momentum coupling and recoupling coefficients

We describe a Scheme implementation of the interactive environment to calculate analytically the Clebsch-Gordan coefficients, Wigner 6j and 9j symbols, and general recoupling coefficients that are used in the quantum theory of angular momentum. The orthogonality conditions for considered coefficients are implemented. The program provides a fast and exact calculation of the coefficients for large values of quantum angular momenta.

Program summary

Title of program:Scheme2ClebschCatalogue number:ADWCProgram summary URL:http://cpc.cs.qub.ac.uk/summaries/ADWCProgram obtainable from:CPC Program Library, Queen's University of Belfast, N. IrelandLicensing provisions:noneComputer for which the program is designed:Any Scheme-capable platformOperating systems under which the program has been tested: Windows 2000Programming language used:SchemeMemory required to execute with typical data:50 MB (≈ size of DrScheme, version 204)No. of lines in distributed program, including test data, etc.: 2872No. of bytes in distributed program, including test data, etc.: 109 396Distribution format:tar.gzNature of physical problem:The accurate and fast calculation of the angular momentum coupling and recoupling coefficients is required in various branches of quantum many-particle physics. The presented code provides a fast and exact calculation of the angular momentum coupling and recoupling coefficients for large values of quantum angular momenta and is based on the GNU Library General Public License PLT software http://www.plt-scheme.org/.Method of solution:A direct evaluation of sum formulas. A general angular momentum recoupling coefficient for an arbitrary number of (integer or half-integer) angular momenta is expressed as a sum over products of the Clebsch-Gordan coefficients.Restrictions on the complexity of the problem:Limited only by the DrScheme implementation used to run the program. No limitation inherent in the code.Typical running time:The Clebsch-Gordan coefficients, Wigner 6j and 9j symbols, and general recoupling coefficients with small angular momenta are computed almost instantaneously. The running time for large-scale calculations depends strongly on the number and magnitude of arguments' values (i.e., of the angular momenta).     

New improved algorithm for the iterative solution of a system of linear algebraic equations

The Coulomb functions f(?,l;?) and g(?,l;?) are required for applications of quantum defect theory; ? is the Z-scaled energy, l the angular momentum quantum number and ? the Z-scaled radial coordinate. The functions f and g are analytic in ?. Power-series expansions are used to compute f and g and their derivatives with respect to ?. The computed value of the Wronskian gives an indication of the accuracy achieved.     

Quantum lattice gas approach for the Maxwell equations

We show that a quantum lattice gas approach can provide a viable means for numerically solving the classical Maxwell equations. By casting the Maxwell equations in Dirac form, the propagator may be discretized, and we describe how the accuracy relative to the time step may be systematically increased. The quantum lattice gas form of the discretization is suitable for implementation on hybrid classical-quantum computers. We discuss a number of extensions, including application to inhomogeneous media.      

The Sturm-Liouville Eigenvalue Problem and NP-Complete Problems in the Quantum Setting with Queries

We show how a number of NP-complete as well as NP-hard problems can be reduced to the Sturm-Liouville eigenvalue problem in the quantum setting with queries. We consider power queries which are derived from the propagator of a system evolving with a Hamiltonian obtained from the discretization of the Sturm-Liouville operator. We use results of our earlier paper concering the complexity of the Sturm-Liouville eigenvalue problem. We show that the number of power queries as well the number of qubits needed to solve the problems studied in this paper is a low degree polynomial. The implementation of power queries by a polynomial number of elementary quantum gates is an open issue. If this problem is solved positively for the power queries used for the Sturm-Liouville eigenvalue problem then a quantum computer would be a very powerful computation device allowing us to solve NP-complete problems in polynomial time.      

Propagator approach for time evolving wave packets in the quantum kicked rotator

We outline a method for time evolving narrow wave packets in the quantum-mechanical kicked rotator, an archetype of quantum chaos. We employ the approximation that the boundary conditions may be neglected. The evolution between kicks may then be carried out using the one-dimensional free-particle propagator.     

Dark energy from instantons

We show that in imaginary time quantum metric fluctuations of empty space form a self-consistent de Sitter gravitational instanton that can be thought of as describing tunneling from “nothing” into de Sitter space of real time (no cosmological constant or scalar fields are needed). For the first time, this mechanism is activated to give birth to a flat inflationary Universe. For the second time, it is turned on to complete the cosmological evolution after the energy density of matter drops below the threshold (the energy density of instantons). A cosmological expansion with dark energy takes over after the scale factor exceeds this threshold, which marks the birth of dark energy at a redshift 1 + z ≈ 1.3 and provides a possible solution to the “coincidence problem”. The number of gravitons which tunneled into the Universe must be of the order of 10¹²² to create the observed value of the Hubble constant. This number has nothing to do with vacuum energy, which is a possible solution to the “old cosmological constant problem”. The emptying Universe should possibly complete its evolution by tunneling back to “nothing”. After that, the entire scenario is repeated, and it can happen endlessly.     

A new computational strategy for ab-initio MRD-CI calculations for breaking a chemical bond in a molecule in a crystal or other solid environment

Recently we derived, implemented, tested and used successfully a new computational strategy for ab-initio MRD-CI (multireference double excitation-configuration interaction) calculations for molecular decompositions of large molecules and intermolecular reactions of large systems. We carry out the ab-initio SCF for the entire system, then transform the canonical delocalized molecular orbitals to localized orbitals and include explicitly in the MRD-CI only the localized occupied and virtual orbitals in the region of interest, folding the remainder of the occupied localized orbitals into an “effective” CI Hamiltonian. The advantage is that the transformations from integrals over atomic orbitals to integrals over molecular orbitals (the computer time-, computer core- and external storage-consuming part of the CI calculations) only have to be carried out for the localized orbitals included explicitly in the MRD-CI calculations.The challenge arose to extend our MRD-CI technique based on localized/local orbitals and “effective” CI Hamiltonian to the breaking of a chemical bond in a molecule in a crystal (or other solid environment). This past year we have derived, implemented and used successfully a procedure for doing this.Our technique involves solving a quantum chemical ab-initio SCF explicitly for a system of a reference molecule surrounded by a number of other molecules in the multipole environment of yet more further out surrounding molecules. The resulting canonical molecular orbitals are then localized and the localized occupied and virtual orbitals in the region of interest are included explicitly in the MRD-CI with the remainder of the occupied localized orbitals being folded into an “effective” CI Hamiltonian. The MRD-I calculations are then carried out for breaking a bond in the reference molecule. This method is completely general. The space treated explicitly quantum chemically and the surrounding space can have defects, deformations, dislocations, impurities, dopants, edges and surfaces, boundaries, etc.We have applied this procedure successfully to the H₃CNO₂ bond dissociation of nitromethane with extensive testing of the number of molecules that have to be included explicitly in the SCF and how many further out molecules have to be represented by multipoles.To check the goodness of the model cluster approximation for crystalline nitromethane, we carried out ab-initio crystal orbital (XTLORB) calculations using our POLY-CRYST program. The difference in the XTLORB total energies between the 4 nitromethane molecules/unit cell and the 3 nitromethane molecules/unit cell, E_R = E₄ − E₃ = − 48.0609079 a.u., corresponds very closely to the reduced energy per nitromethane molecule, E_R = − 48.06057 a.u., calculated from explicit SCF calculations on the model nitromethane cluster in the multipole field of farther out nitromethane molecules for the model cluster.Thus, the multipole approximation for describing the effect of further out molecules on the SCF cluster energies is quite good.     

Approximate inference in Boltzmann machines

Inference in Boltzmann machines is NP-hard in general. As a result approximations are often necessary. We discuss first order mean field and second order Onsager truncations of the Plefka expansion of the Gibbs free energy. The Bethe free energy is introduced and rewritten as a Gibbs free energy. From there a convergent belief optimization algorithm is derived to minimize the Bethe free energy. An analytic expression for the linear response estimate of the covariances is found which is exact on Boltzmann trees. Finally, a number of theorems is proven concerning the Plefka expansion, relating the first order mean field and the second order Onsager approximation to the Bethe approximation. Experiments compare mean field approximation, Onsager approximation, belief propagation and belief optimization.     

Implementing logical connectives in constraint programming

Combining constraints using logical connectives such as disjunction is ubiquitous in constraint programming, because it adds considerable expressive power to a constraint language. We explore the solver architecture needed to propagate such combinations of constraints efficiently. In particular we describe two new features named satisfying sets and constraint trees. We also make use of movable triggers (Gent et al., 2006) [1], and with these three complementary features we are able to make considerable efficiency gains.A key reason for the success of Boolean Satisfiability (SAT) solvers is their ability to propagate Or constraints efficiently, making use of movable triggers. We successfully generalise this approach to an Or of an arbitrary set of constraints, maintaining the crucial property that at most two constraints are active at any time, and no computation at all is done on the others. We also give an And propagator within our framework, which may be embedded within the Or. Using this approach, we demonstrate speedups of over 10,000 times in some cases, compared to traditional constraint programming approaches. We also prove that the Or algorithm enforces generalised arc consistency (GAC) when all its child constraints have a GAC propagator, and no variables are shared between children. By extending the Or propagator, we present a propagator for AtLeastK, which expresses that at least k of its child constraints are satisfied in any solution.Some logical expressions (e.g. exclusive-or) cannot be compactly expressed using And, Or and AtLeastK. Therefore we investigate reification of constraints. We present a fast generic algorithm for reification using satisfying sets and movable triggers.     

Unitarity plus causality implies localizability

We consider a graph with a single quantum system at each node. The entire compound system evolves in discrete time steps by iterating a global evolution U. We require that this global evolution U be unitary, in accordance with quantum theory, and that this global evolution U be causal, in accordance with special relativity. By causal we mean that information can only ever be transmitted at a bounded speed, the speed bound being quite naturally that of one edge of the underlying graph per iteration of U. We show that under these conditions the operator U can be implemented locally; i.e. it can be put into the form of a quantum circuit made up with more elementary operators — each acting solely upon neighboring nodes. We take quantum cellular automata as an example application of this representation theorem: this analysis bridges the gap between the axiomatic and the constructive approaches to defining QCA.     

A Poisson Integrator for Gaussian Wavepacket Dynamics

We consider the variational approximation~of the time-dependent Schrödinger equation by Gaussians wavepackets. The corresponding finite-dimensional dynamical system inherits a Poisson (or non-canonically symplectic) structure from the Schrödinger equation by its construction via the Dirac–Frenkel–McLachlan variational principle. The variational splitting between kinetic and potential energy turns out to yield an explicit, easily implemented numerical scheme. This method is a time-reversible Poisson integrator, which also preserves the L ² norm and linear and angular momentum. Using backward error analysis, we show long-time energy conservation for this splitting scheme. In the semi-classical limit the numerical approximations to position and momentum converge to those obtained by applying the Störmer–Verlet method to the classical limit system.     

Kinetic heap-ordered trees: Tight analysis and improved algorithms

The most natural kinetic data structure for maintaining the maximum of a collection of continuously changing numbers is the kinetic heap. Basch, Guibas, and Ramkumar proved that the maximum number of events processed by a kinetic heap with n numbers changing as linear functions of time is O(nlog²n) and . We prove that this number is actually Θ(nlogn). In the kinetic heap, a linear number of events are stored in a priority queue, consequently, it takes O(logn) time to determine the next event at each iteration. We also present a modified version of the kinetic heap that processes O(nlogn/loglogn) events, with the same O(logn) time complexity to determine the next event.     

A method for solving the molecular Schrödinger equation in Cartesian coordinates via angular momentum projection operators

A method for solving the Schrödinger equation of N-atom molecules in 3N−3 Cartesian coordinates usually defined by Jacobi vectors is presented. The separation and conservation of the total angular momentum are obtained not by transforming the Hamiltonian in internal curvilinear coordinates but instead, by keeping the Cartesian formulation of the Hamiltonian operator and projecting the initial wavefunction onto the proper irreducible representation angular momentum subspace. The increased number of degrees of freedom from 3N−6 to 3N−3, compared to previous methods for solving the Schrödinger equation, is compensated by the simplicity of the kinetic energy operator and its finite difference representations which result in sparse Hamiltonian matrices. A parallel code in Fortran 95 has been developed and tested for model potentials of harmonic oscillators. Moreover, we compare data obtained for the three-dimensional hydrogen molecule and the six-dimensional water molecule with results from the literature. The availability of large clusters of computers with hundreds of CPUs and GBytes of memory, as well as the rapid development of distributed (Grid) computing, make the proposed method, which is unequivocally highly demanding in memory and computer time, attractive for studying Quantum Molecular Dynamics.     

Exact and Approximation Algorithms for Geometric and Capacitated Set Cover Problems

First, we study geometric variants of the standard set cover motivated by assignment of directional antenna and shipping with deadlines, providing the first known polynomial-time exact solutions. Next, we consider the following general (non-necessarily geometric) capacitated set cover problem. There is given a set of elements with real weights and a family of sets of the elements. One can use a set if it is a subset of one of the sets in the family and the sum of the weights of its elements is at most one. The goal is to cover all the elements with the allowed sets. We show that any polynomial-time algorithm that approximates the uncapacitated version of the set cover problem with ratio r can be converted to an approximation algorithm for the capacitated version with ratio r+1.357. In particular, the composition of these two results yields a polynomial-time approximation algorithm for the problem of covering a set of customers represented by a weighted n-point set with a minimum number of antennas of variable angular range and fixed capacity with ratio?2.357. This substantially improves on the best known approximation ratio for the latter antenna problem equal to?3. Furthermore, we provide a PTAS for the dual problem where the number of sets (e.g., antennas) to use is fixed and the task is to minimize the maximum set load, in case the sets correspond to line intervals or arcs. Finally, we discuss the approximability of the generalization of the antenna problem to include several base stations for antennas, and in particular show its APX-hardness already in the uncapacitated case.     

Two-machine flow-shop scheduling with rejection

We study a scheduling problem with rejection on a set of two machines in a flow-shop scheduling system. We evaluate the quality of a solution by two criteria: the first is the makespan and the second is the total rejection cost. We show that the problem of minimizing the makespan plus total rejection cost is NP-hard and for its solution we provide two different approximation algorithms, a pseudo-polynomial time optimization algorithm and a fully polynomial time approximation scheme (FPTAS). We also study the problem of finding the entire set of Pareto-optimal points (this problem is NP-hard due to the NP-hardness of the same problem variation on a single machine [20]). We show that this problem can be solved in pseudo-polynomial time. Moreover, we show how we can provide an FPTAS that, given that there exists a Pareto optimal schedule with a total rejection cost of at most R and a makespan of at most K, finds a solution with a total rejection cost of at most (1+?)R and a makespan value of at most (1+?)K. This is done by defining a set of auxiliary problems and providing an FPTAS algorithm to each one of them.     

Approximate Guarding of Monotone and Rectilinear Polygons

We show that vertex guarding a monotone polygon is NP-hard and construct a constant factor approximation algorithm for interior guarding monotone polygons. Using this algorithm we obtain an approximation algorithm for interior guarding rectilinear polygons that has an approximation factor independent of the number of vertices of the polygon. If the size of the smallest interior guard cover is OPT for a rectilinear polygon, our algorithm produces a guard set of size O(OPT ²).     

Minimizing Energies with Hierarchical Costs

Computer vision is full of problems elegantly expressed in terms of energy minimization. We characterize a class of energies with hierarchical costs and propose a novel hierarchical fusion algorithm. Hierarchical costs are natural for modeling an array of difficult problems. For example, in semantic segmentation one could rule out unlikely object combinations via hierarchical context. In geometric model estimation, one could penalize the number of unique model families in a solution, not just the number of models??a kind of hierarchical MDL criterion. Hierarchical fusion uses the well-known ??-expansion algorithm as a subroutine, and offers a much better approximation bound in important cases.     

Semi-asynchronous and distributed weighted connected dominating set algorithms for wireless sensor networks

Energy-efficient backbone construction is one of the most important objective in a wireless sensor network (WSN) and to construct a more robust backbone, weighted connected dominating sets can be used where the energy of the nodes are directly related to their weights. In this study, we propose algorithms for this purpose and classify our algorithms as weighted dominating set algorithms and weighted Steiner tree algorithms where these algorithms are used together to construct a weighted connected dominating set (WCDS). We provide fully distributed algorithms with semi-asynchronous versions. We show the design of the algorithms, analyze their proof of correctness, time, message and space complexities and provide the simulation results in ns2 environment. We show that the approximation ratio of our algorithms is 3ln(S) where S is the total weight of optimum solution. To the best of our knowledge, our algorithms are the first fully distributed and semi-asynchronous WCDS algorithms with 3ln(S) approximation ratio. We compare our proposed algorithms with the related work and show that our algorithms select backbone with lower cost and less number of nodes.     

Solving the gluon Dyson—Schwinger equation in the Mandelstam approximation

Truncated Dyson—Schwinger equations represent finite subsets of the equations of motion for Green's functions. Solutions to these nonlinear integral equations can account for nonperturbative correlations. We describe the solution to the Dyson—Schwinger equation for the gluon propagator of Landau gauge QCD in the Mandelstam approximation. This involves a combination of numerical and analytic methods: an asymptotic infrared expansion of the solution is calculated recursively. In the ultraviolet, the problem reduces to an analytically solvable differential equation. The iterative solution is then obtained numerically by matching it to the analytic results at appropriate points. Matching point independence is obtained for sufficiently wide ranges. The solution is used to extract a nonperturbative β-function. The scaling behavior is in good agreement with perturbative QCD. No further fixed point for positive values of the coupling is found which thus increases without bound in the infrared. The nonperturbative result implies an infrared singular quark interaction relating the scale A of the subtraction scheme to the string tension σ.     

Instance variant nearest neighbor using particle swarm optimization for function approximation

In this paper, a new approach called ‘instance variant nearest neighbor’ approximates a regression surface of a function using the concept of k nearest neighbor. Instead of fixed k neighbors for the entire dataset, our assumption is that there are optimal k neighbors for each data instance that best approximates the original function by fitting the local regions. This approach can be beneficial to noisy datasets where local regions form data characteristics that are different from the major data clusters. We formulate the problem of finding such k neighbors for each data instance as a combinatorial optimization problem, which is solved by a particle swarm optimization. The particle swarm optimization is extended with a rounding scheme that rounds up or down continuous-valued candidate solutions to integers, a number of k neighbors. We apply our new approach to five real-world regression datasets and compare its prediction performance with other function approximation algorithms, including the standard k nearest neighbor, multi-layer perceptron, and support vector regression. We observed that the instance variant nearest neighbor outperforms these algorithms in several datasets. In addition, our new approach provides consistent outputs with five datasets where other algorithms perform poorly.