Mv
M.J. van Loenen
info
Please Note
<p>This page displays the records of the person named above and is not linked to a unique person identifier. This record may need to be merged to a profile.</p>
2 records found
1
Parameter Optimization for Quantum Annealing
Experimental research on the effects of the Lagrangian multiplier, annealing schedule and the embedding on the performance of standard and reverse quantum annealing
Quantum annealing is the continuous transformation of the energy working on a quantum system and then measuring said system. The adiabatic theorem and the Ising model let us leverage quantum annealing to find minimal solutions to quadratic unconstrained binary optimization (QUBO) models by setting the energy present during quantum annealing. In this thesis we investigate the QUBO-dization of the multiple object tracking (MOT) problem and perform parameter optimization on the Lagrangian multiplier, chain strength and annealing time parameters as well as test the effects on quantum annealing performance acquired by adding a pause or quench to the anneal schedule or by performing reverse annealing. Experiments were performed on state of the art quantum annealers developed by D-Wave and MOT problem instances were made by us to provide minimally preprocessed QUBO matrices. Reverse annealing was found to have a better performance than standard anneal schedules and we perceived a relation between the annealing time and quantum annealing performance. During testing we found additional factors that contribute to the performance such as the embedding of the Ising model onto the qubits of the quantum annealer. We combine our findings to provide a full quantum annealing schedule and initial state suitable for quantum annealing on state of the art quantum annealers developed by D-Wave.
...
Quantum annealing is the continuous transformation of the energy working on a quantum system and then measuring said system. The adiabatic theorem and the Ising model let us leverage quantum annealing to find minimal solutions to quadratic unconstrained binary optimization (QUBO) models by setting the energy present during quantum annealing. In this thesis we investigate the QUBO-dization of the multiple object tracking (MOT) problem and perform parameter optimization on the Lagrangian multiplier, chain strength and annealing time parameters as well as test the effects on quantum annealing performance acquired by adding a pause or quench to the anneal schedule or by performing reverse annealing. Experiments were performed on state of the art quantum annealers developed by D-Wave and MOT problem instances were made by us to provide minimally preprocessed QUBO matrices. Reverse annealing was found to have a better performance than standard anneal schedules and we perceived a relation between the annealing time and quantum annealing performance. During testing we found additional factors that contribute to the performance such as the embedding of the Ising model onto the qubits of the quantum annealer. We combine our findings to provide a full quantum annealing schedule and initial state suitable for quantum annealing on state of the art quantum annealers developed by D-Wave.
Markov chains are used to describe random processes in discrete time, which have the property of being memoryless. This report covers Markov chains on a finite space that are homogeneous in time and mainly follows the structure of ''Markov Chains and Mixing Times''. Markov chains exhibit a strong connection with electric networks. We exploit such a connection and apply the laws of physics to answer several probabilistic questions about random walks, which are certain types of Markov chains. This connection is then called the electric network approach and is built on translating the random walk into an electric network by relating the transition probability to the so-called conductance. The electric network approach provides problem simplification tools, such as the Series/Parallel Law, and powerful inequalities, such as the Nash-Williams inequality. These tools are based on physics and are often more intuitive than their probabilistic counterpart.
We simulate a two-dimensional random walk that starts at the center of a square and ''escapes'' if it reaches the perimeter of the square before returning to the center. We then compare this escape probability to an upper bound, which results from using the Nash-Williams inequality. The sharpness of the upper bound depends on the choice of edge-cutsets. We find that choosing edge-cutsets with a minimal amount of edges gives a sharper upper bound, than choosing edge-cutsets that contain all the edges of the square. The relation between the upper bound and the escape probability seems to be independent of the size of the square. Furthermore, we provide proofs that are not explicit in ''Markov Chains and Mixing Times'' and ''Reversible Markov Chains and Random Walks on Graphs'' and add to the contents of ''Markov Chains and Mixing Times'' by studying random walks from a graph theory perspective. ...
We simulate a two-dimensional random walk that starts at the center of a square and ''escapes'' if it reaches the perimeter of the square before returning to the center. We then compare this escape probability to an upper bound, which results from using the Nash-Williams inequality. The sharpness of the upper bound depends on the choice of edge-cutsets. We find that choosing edge-cutsets with a minimal amount of edges gives a sharper upper bound, than choosing edge-cutsets that contain all the edges of the square. The relation between the upper bound and the escape probability seems to be independent of the size of the square. Furthermore, we provide proofs that are not explicit in ''Markov Chains and Mixing Times'' and ''Reversible Markov Chains and Random Walks on Graphs'' and add to the contents of ''Markov Chains and Mixing Times'' by studying random walks from a graph theory perspective. ...
Markov chains are used to describe random processes in discrete time, which have the property of being memoryless. This report covers Markov chains on a finite space that are homogeneous in time and mainly follows the structure of ''Markov Chains and Mixing Times''. Markov chains exhibit a strong connection with electric networks. We exploit such a connection and apply the laws of physics to answer several probabilistic questions about random walks, which are certain types of Markov chains. This connection is then called the electric network approach and is built on translating the random walk into an electric network by relating the transition probability to the so-called conductance. The electric network approach provides problem simplification tools, such as the Series/Parallel Law, and powerful inequalities, such as the Nash-Williams inequality. These tools are based on physics and are often more intuitive than their probabilistic counterpart.
We simulate a two-dimensional random walk that starts at the center of a square and ''escapes'' if it reaches the perimeter of the square before returning to the center. We then compare this escape probability to an upper bound, which results from using the Nash-Williams inequality. The sharpness of the upper bound depends on the choice of edge-cutsets. We find that choosing edge-cutsets with a minimal amount of edges gives a sharper upper bound, than choosing edge-cutsets that contain all the edges of the square. The relation between the upper bound and the escape probability seems to be independent of the size of the square. Furthermore, we provide proofs that are not explicit in ''Markov Chains and Mixing Times'' and ''Reversible Markov Chains and Random Walks on Graphs'' and add to the contents of ''Markov Chains and Mixing Times'' by studying random walks from a graph theory perspective.
We simulate a two-dimensional random walk that starts at the center of a square and ''escapes'' if it reaches the perimeter of the square before returning to the center. We then compare this escape probability to an upper bound, which results from using the Nash-Williams inequality. The sharpness of the upper bound depends on the choice of edge-cutsets. We find that choosing edge-cutsets with a minimal amount of edges gives a sharper upper bound, than choosing edge-cutsets that contain all the edges of the square. The relation between the upper bound and the escape probability seems to be independent of the size of the square. Furthermore, we provide proofs that are not explicit in ''Markov Chains and Mixing Times'' and ''Reversible Markov Chains and Random Walks on Graphs'' and add to the contents of ''Markov Chains and Mixing Times'' by studying random walks from a graph theory perspective.