Determining Acceptance Possibility for a Quantum Computation is Hard for the Polynomial Hierarchy

It is shown that determining whether a quantum computation has a non-zero probability of accepting is at least as hard as the polynomial time hierarchy. This hardness result also applies to determining in general whether a given quantum basis state appears with nonzero amplitude in a superposition, or whether a given quantum bit has positive expectation value at the end of a quantum computation. This result is achieved by showing that the complexity class NQP of Adleman, Demarrais, and Huang, a quantum analog of NP, is equal to the counting class coC=P.

Deciding Isomorphisms of Simple Types in Polynomial Time

The isomorphisms holding in all models of the simply typed lambda calculus with surjective and terminal objects are well studied - these models are exactly the Cartesian closed categories. Isomorphism of two simple types in such a model is decidable by reduction to a normal form and comparison under a finite number of permutations (Bruce, Di Cosmo, and Longo 1992). Unfortunately, these normal forms may be exponentially larger than the original types so this construction decides isomorphism in exponential time. We show how using space-sharing/hash-consing techniques and memoization can be used to decide isomorphism in practical polynomial time (low degree, small hidden constant). Other researchers have investigated simple type isomorphism in relation to, among other potential applications, type-based retrieval of software modules from libraries and automatic generation of bridge code for multi-language systems. Our result makes such potential applications practically feasible.

Orthogonal orientation control of carbon nanotube growth.

Carbon nanotubes (CNTs) have attracted attention for their remarkable electrical properties and have being explored as one of the best building blocks in nano-electronics. A key challenge to realize such potential is the control of the nanotube growth directions. Even though both vertical growth and controlled horizontal growth of carbon nanotubes have been realized before, the growth of complex nanotube structures with both vertical and horizontal orientation control on the same substrate has never been achieved. Here, we report a method to grow three-dimensional (3D) complex nanotube structures made of vertical nanotube forests and horizontal nanotube arrays on a single substrate and from the same catalyst pattern by an orthogonally directed nanotube growth method using chemical vapor deposition (CVD). More importantly, such a capability represents a major advance in controlled growth of carbon nanotubes. It enables researchers to control the growth directions of nanotubes by simply changing the reaction conditions. The high degree of control represented in these experiments will surely make the fabrication of complex nanotube devices a possibility.

Reformulating time-dependent density functional theory with non-orthogonal localized molecular orbitals.

Time-dependent density functional theory (TDDFT) has broad application in the study of electronic response, excitation and transport. To extend such application to large and complex systems, we develop a reformulation of TDDFT equations in terms of non-orthogonal localized molecular orbitals (NOLMOs). NOLMO is the most localized representation of electronic degrees of freedom and has been used in ground state calculations. In atomic orbital (AO) representation, the sparsity of NOLMO is transferred to the coefficient matrix of molecular orbitals (MOs). Its novel use in TDDFT here leads to a very simple form of time propagation equations which can be solved with linear-scaling effort. We have tested the method for several long-chain saturated and conjugated molecular systems within the self-consistent charge density-functional tight-binding method (SCC-DFTB) and demonstrated its accuracy. This opens up pathways for TDDFT applications to large bio- and nano-systems.

A polynomial algorithm for the three-machine open shop with a bottleneck machine

The paper considers the three‐machine open shop scheduling problem to minimize themakespan. It is assumed that each job consists of at most two operations, one of which is tobe processed on the bottleneck machine, the same for all jobs. A new lower bound on theoptimal makespan is derived, and a linear‐time algorithm for finding an optimalnon‐preemptive schedule is presented.

A fully polynomial approximation scheme for the single machine weighted total tardiness problem with a common due date

We develop a fully polynomial-time approximation scheme (FPTAS) for minimizing the weighted total tardiness on a single machine, provided that all due dates are equal. The FPTAS is obtained by converting an especially designed pseudopolynomial dynamic programming algorithm.

The conjugacy problem for two-by-two matrices over polynomial rings

We give an effective solution of the conjugacy problem for two-by-two matrices over the polynomial ring in one variable over a finite field.