Current Search: quantum algorithm (x)
View All Items
- Title
- STUDIES OF A QUANTUM SCHEDULING ALGORITHM AND ON QUANTUM ERROR CORRECTION.
- Creator
-
Lu, Feng, Marinescu, Dan, University of Central Florida
- Abstract / Description
-
Quantum computation has been a rich field of study for decades because it promises possible spectacular advances, some of which may run counter to our classically rooted intuitions. At the same time, quantum computation is still in its infancy in both theoretical and practical areas. Efficient quantum algorithms are very limited in number and scope; no real breakthrough has yet been achieved in physical implementations. Grover's search algorithm can be applied to a wide range of problems;...
Show moreQuantum computation has been a rich field of study for decades because it promises possible spectacular advances, some of which may run counter to our classically rooted intuitions. At the same time, quantum computation is still in its infancy in both theoretical and practical areas. Efficient quantum algorithms are very limited in number and scope; no real breakthrough has yet been achieved in physical implementations. Grover's search algorithm can be applied to a wide range of problems; even problems not generally regarded as searching problems can be reformulated to take advantage of quantum parallelism and entanglement leading to algorithms which show a square root speedup over their classical counterparts. This dissertation discusses a systematic way to formulate such problems and gives as an example a quantum scheduling algorithm for an R||C_max problem. This thesis shows that quantum solution to such problems is not only feasible but in some cases advantageous. The complexity of the error correction circuitry forces us to design quantum error correction codes capable of correcting only a single error per error correction cycle. Yet, time-correlated errors are common for physical implementations of quantum systems; an error corrected during a certain cycle may reoccur in a later cycle due to physical processes specific to each physical implementation of the qubits. This dissertation discusses quantum error correction for a restricted class of time-correlated errors in a spin-boson model. The algorithm proposed allows the correction of two errors per error correction cycle, provided that one of them is time-correlated. The algorithm can be applied to any stabilizer code, perfect or non-perfect, and simplified the circuit complexity significantly comparing to the classic quantum error correction codes.
Show less - Date Issued
- 2007
- Identifier
- CFE0001873, ucf:47391
- Format
- Document (PDF)
- PURL
- http://purl.flvc.org/ucf/fd/CFE0001873
- Title
- The Power of Quantum Walk: Insights, Implementation, and Applications.
- Creator
-
Chiang, Chen-Fu, Wocjan, Pawel, Marinescu, Dan, Dechev, Damian, Mucciolo, Eduardo, University of Central Florida
- Abstract / Description
-
In this thesis, I investigate quantum walks in quantum computing from threeaspects: the insights, the implementation, and the applications. Quantum walks are the quantum analogue of classical random walks. For the insights of quantum walks, I list and explain the required components for quantizing a classical random walk into a quantum walk. The components are, for instance, Markov chains, quantum phase estimation, and quantum spectrum theorem. I then demonstrate how the product of two...
Show moreIn this thesis, I investigate quantum walks in quantum computing from threeaspects: the insights, the implementation, and the applications. Quantum walks are the quantum analogue of classical random walks. For the insights of quantum walks, I list and explain the required components for quantizing a classical random walk into a quantum walk. The components are, for instance, Markov chains, quantum phase estimation, and quantum spectrum theorem. I then demonstrate how the product of two reflections in the walk operator provides a quadratic speed-up, in comparison to the classical counterpart. For the implementation of quantum walks, I show the construction of an efficient circuit for realizing one single step of the quantum walk operator. Furthermore, I devise a more succinct circuit to approximately implement quantum phase estimation with constant precision controlled phase shift operators. From an implementation perspective, efficient circuits are always desirable because the realization of a phase shift operator with high precision would be a costly task and a critical obstacle. For the applications of quantum walks, I apply the quantum walk technique along with other fundamental quantum techniques, such as phase estimation, to solve the partition function problem. However, there might be some scenario in which the speed-up of spectral gap is insignificant. In a situation like that that,I provide an amplitude amplification-based approach to prepare the thermal Gibbs state. Such an approach is useful when the spectral gap is extremely small. Finally, I further investigate and explore the effect of noise (perturbation)on the performance of quantum walks.
Show less - Date Issued
- 2011
- Identifier
- CFE0004094, ucf:49148
- Format
- Document (PDF)
- PURL
- http://purl.flvc.org/ucf/fd/CFE0004094
- Title
- Quantum Algorithms for: Quantum Phase Estimation, Approximation of the Tutte Polynomial and Black-box Structures.
- Creator
-
Ahmadi Abhari, Seyed Hamed, Brennan, Joseph, Mucciolo, Eduardo, Li, Xin, Marinescu, Dan, University of Central Florida
- Abstract / Description
-
In this dissertation, we investigate three different problems in the field of Quantum computation. First, we discuss the quantum complexity of evaluating the Tutte polynomial of a planar graph. Furthermore, we devise a new quantum algorithm for approximating the phase of a unitary matrix. Finally, we provide quantum tools that can be utilized to extract the structure of black-box modules and algebras. While quantum phase estimation (QPE) is at the core of many quantum algorithms known to date...
Show moreIn this dissertation, we investigate three different problems in the field of Quantum computation. First, we discuss the quantum complexity of evaluating the Tutte polynomial of a planar graph. Furthermore, we devise a new quantum algorithm for approximating the phase of a unitary matrix. Finally, we provide quantum tools that can be utilized to extract the structure of black-box modules and algebras. While quantum phase estimation (QPE) is at the core of many quantum algorithms known to date, its physical implementation (algorithms based on quantum Fourier transform (QFT)) is highly constrained by the requirement of high-precision controlled phase shift operators, which remain difficult to realize. In the second part of this dissertation, we introduce an alternative approach to approximately implement QPE with arbitrary constant-precision controlled phase shift operators.The new quantum algorithm bridges the gap between QPE algorithms based on QFT and Kitaev's original approach. For approximating the eigenphase precise to the nth bit, Kitaev's original approach does not require any controlled phase shift operator. In contrast, QPE algorithms based on QFT or approximate QFT require controlled phase shift operators with precision of at least Pi/2n. The new approach fills the gap and requires only arbitrary constant-precision controlled phase shift operators. From a physical implementation viewpoint, the new algorithm outperforms Kitaev's approach.The other problem we investigate relates to approximating the Tutte polynomial. We show that the problem of approximately evaluating the Tutte polynomial of triangular graphs at the points (q,1/q) of the Tutte plane is BQP-complete for (most) roots of unity q. We also consider circular graphs and show that the problem of approximately evaluating the Tutte polynomial of these graphs at a point is DQC1-complete and at some points is in BQP.To show that these problems can be solved by a quantum computer, we rely on the relation of the Tutte polynomial of a planar G graph with the Jones and HOMFLY polynomial of the alternating link D(G) given by the medial graph of G. In the case of our graphs the corresponding links are equal to the plat and trace closures of braids. It is known how to evaluate the Jones and HOMFLY polynomial for closures of braids.To establish the hardness results, we use the property that the images of the generators of the braid group under the irreducible Jones-Wenzl representations of the Hecke algebra have finite order. We show that for each braid we can efficiently construct a braid such that the evaluation of the Jones and HOMFLY polynomials of their closures at a fixed root of unity leads to the same value and that the closures of the resulting braid are alternating links.The final part of the dissertation focuses on finding the structure of a black-box module or algebra. Suppose we are given black-box access to a finite module M or algebra over a finite ring R and a list of generators for M and R. We show how to find a linear basis and structure constants for M in quantum poly (log|M|) time. This generalizes a recent quantum algorithm of Arvind et al. which finds a basis representation for rings. We then show that our algorithm is a useful primitive allowing quantum computer to determine the structure of a finite associative algebra as a direct sum of simple algebras. Moreover, it solves a wide variety of problems regarding finite modules and rings. Although our quantum algorithm is based on Abelian Fourier transforms, it solves problems regarding the multiplicative structure of modules and algebras, which need not be commutative. Examples include finding the intersection and quotient of two modules, finding the additive and multiplicative identities in a module, computing the order of an module, solving linear equations over modules, deciding whether an ideal is maximal, finding annihilators, and testing the injectivity and surjectivity of ring homomorphisms. These problems appear to be exponentially hard classically.
Show less - Date Issued
- 2012
- Identifier
- CFE0004239, ucf:49526
- Format
- Document (PDF)
- PURL
- http://purl.flvc.org/ucf/fd/CFE0004239
- Title
- Solving Constraint Satisfaction Problems with Matrix Product States.
- Creator
-
Pelton, Sabine, Mucciolo, Eduardo, Ishigami, Masa, Leuenberger, Michael, University of Central Florida
- Abstract / Description
-
In the past decade, Matrix Product State (MPS) algorithms have emerged as an efficient method of modeling some many-body quantum spin systems. Since spin system Hamiltonians can be considered constraint satisfaction problems (CSPs), it follows that MPS should provide a versatile framework for studying a variety of general CSPs. In this thesis, we apply MPS to two types of CSP. First, use MPS to simulate adiabatic quantum computation (AQC), where the target Hamiltonians are instances of a...
Show moreIn the past decade, Matrix Product State (MPS) algorithms have emerged as an efficient method of modeling some many-body quantum spin systems. Since spin system Hamiltonians can be considered constraint satisfaction problems (CSPs), it follows that MPS should provide a versatile framework for studying a variety of general CSPs. In this thesis, we apply MPS to two types of CSP. First, use MPS to simulate adiabatic quantum computation (AQC), where the target Hamiltonians are instances of a fully connected, random Ising spin glass. Results of the simulations help shed light on why AQC fails for some optimization problems. We then present the novel application of a modified MPS algorithm to classical Boolean satisfiability problems, specifically k-SAT and max k-SAT. By construction, the algorithm also counts solutions to a given Boolean formula (\#-SAT). For easy satisfiable instances, the method is more expensive than other existing algorithms; however, for hard and unsatisfiable instances, the method succeeds in finding satisfying assignments where other algorithms fail to converge.
Show less - Date Issued
- 2017
- Identifier
- CFE0006902, ucf:51713
- Format
- Document (PDF)
- PURL
- http://purl.flvc.org/ucf/fd/CFE0006902