Abstract:
Geometric phases accompanying adiabatic processes in quantum systems can be utilized as unitary gates for quantum computation. Optimization of control of the adiabatic process naturally leads to the isoholonomic problem. The isoholonomic problem in a homogeneous fiber bundle is formulated and solved completely.

Abstract:
A general quantum algorithm for solving a problem is discussed. The number of steps required to solve a problem using this method is independent of the number of cases that has to be considered classically. Hence, it is more efficient than existing classical algorithms or quantum algorithm, which requires O(sqrt(N)) steps.

Abstract:
We show that the NP-hard quadratic unconstrained binary optimization (QUBO) problem on a graph $G$ can be solved using an adiabatic quantum computer that implements an Ising spin-1/2 Hamiltonian, by reduction through minor-embedding of $G$ in the quantum hardware graph $U$. There are two components to this reduction: embedding and parameter setting. The embedding problem is to find a minor-embedding $G^{emb}$ of a graph $G$ in $U$, which is a subgraph of $U$ such that $G$ can be obtained from $G^{emb}$ by contracting edges. The parameter setting problem is to determine the corresponding parameters, qubit biases and coupler strengths, of the embedded Ising Hamiltonian. In this paper, we focus on the parameter setting problem. As an example, we demonstrate the embedded Ising Hamiltonian for solving the maximum independent set (MIS) problem via adiabatic quantum computation (AQC) using an Ising spin-1/2 system. We close by discussing several related algorithmic problems that need to be investigated in order to facilitate the design of adiabatic algorithms and AQC architectures.

Abstract:
The NP-complete problem of the travelling salesman (TSP) is considered in the framework of quantum adiabatic computation (QAC). We first derive a remarkable lower bound for the computation time for adiabatic algorithms in general as a function of the energy involved in the computation. Energy, and not just time and space, must thus be considered in the evaluation of algorithm complexity, in perfect accordance with the understanding that all computation is physical. We then propose, with oracular Hamiltonians, new quantum adiabatic algorithms of which not only the lower bound in time but also the energy requirement do not increase exponentially in the size of the input. Such an improvement in both time and energy complexity, as compared to all other existing algorithms for TSP, is apparently due to quantum entanglement. We also appeal to the general theory of Diophantine equations in a speculation on physical implementation of those oracular Hamiltonians.

Abstract:
We develop a classical model of computation (the S model) which captures some important features of quantum computation, and which allows to design fast algorithms for solving specific problems. In particular, we show that Deutsch's problem can be trated within the S model of computation in the same way as within quantum computation; also Grover's search problem of an unsorted database finds a surprisingly fast solution. The correct understanding of these results put into a new perspective the relationship between quantum and classical computation.

Abstract:
We present a framework for efficiently solving Approximate Traveling Salesman Problem (Approximate TSP) for Quantum Computing Models. Existing representations of TSP introduce extra states which do not correspond to any permutation. We present an efficient and intuitive encoding for TSP in quantum computing paradigm. Using this representation and assuming a Gaussian distribution on tour-lengths, we give an algorithm to solve Approximate TSP (Euclidean) within BQP resource bounds. Generalizing this strategy for any distribution, we present an oracle based Quantum Algorithm to solve Approximate TSP. We present a realization of the oracle in the quantum counterpart of PP.

Abstract:
The quantum search problem is an important problem due to the fact that a general NP problem can be solved efficiently by an unsorted quantum search algorithm. Here it has been shown that the quantum search problem could be solved in polynomial time on an NMR quantum computer. The NMR ensemble quantum computation is based on the quantum mechanical unitary dynamics that both a closed quantum system and its ensemble obey the same quantum mechanical unitary dynamics instead of on the pseudopure state or the effective pure state of the classical NMR quantum computation. Based on the new principle the conventional NMR multiple-quantum spectroscopy has been developed to solve experimentally the search problem. The solution information of the search problem is first loaded on the unitary evolution propagator which is constructed with the oracle unitary operation and oracle-independent unitary operations and is used to excite the multiple-quantum coherence in a spin ensemble. Then the multiple- quantum spectroscopy is used to extract experimentally the solution information. It has been discussed how to enhance the output NMR signal of the quantum search NMR multiple-quantum pulse sequence and some approaches to enhancing the NMR signal are also proposed. The present work could be helpful for conventional high field NMR machines to solve efficiently the quantum search problem.

Abstract:
This paper presents a complete algorithmic study of the decision Boolean Satisfiability Problem under the classical computation and quantum computation theories. The paper depicts deterministic and probabilistic algorithms, propositions of their properties and the main result is that the problem has not an efficient algorithm (NP is not P). Novel quantum algorithms and propositions depict that the complexity by quantum computation approach for solving the Boolean Satisfiability Problem or any NP problem is lineal time.

Abstract:
We present a new approach to quantum computation involving the geometric phase. In this approach, an entire computation is performed by adiabatically evolving a suitably chosen quantum system in a closed circuit in parameter space. The problem solved is the determination of the solubility of a 3-SAT Boolean Satisfiability problem. The problem of non-adiabatic transitions to higher levels is addressed in several ways. The avoided level crossings are well defined and the interpolation can be slowed in this region, the Hamiltonian can be scaled with problem dimension resulting in a constant gap size and location, and the prescription here is sufficiently general as to allow for other suitably chosen Hamiltonians. Finally, we show that with $n$ applications of this approach, the geometric phase based quantum computation method may be used to find the solution to the 3-SAT problem in $n$ variables, a member of the NP-complete complexity class.

Abstract:
A hierarchical, reversible mapping between levels of tree structured computation, applicable for structuring the Quantum Computation algorithm for NP-complete problem is presented. It is proven that confining the state of a quantum computer to a subspace of the available Hilbert space, where states are consistent with the problem constraints, can be done in polynomial time. The proposed mapping, together with the method of state reduction can be potentially used for solving NP-complete problems in polynomial time.