{"id":{"repo_id":"calgary","oai_identifier":"oai:ucalgary.scholaris.ca:1880/114117"},"canonical_url":"https://search.dev.ndltd.org/etd/calgary/oai:ucalgary.scholaris.ca:1880/114117","repository":{"repo_id":"calgary","name":"University of Calgary","base_url":"https://ucalgary.scholaris.ca/server/oai/request"},"display":{"title":"Sampling Using Controlled Quantum Walks","abstract":"We give a new quantum algorithm to sample from probability distributions over graph vertices quadratically faster than the optimal classical algorithm, which uses random walks with stopping rules. Efficient sampling is an important computational task used in simulations based on stochastic processes. This is the first quantum algorithm that achieves a quadratic speed-up for sampling from general probability distributions over graph vertices. Our algorithm generalizes the controlled quantum walk algorithm proposed by Dohotaru and Høyer in 2015. Our main technical innovation is to allow for multiple distinct controlled reflections. This allows us to generate the quantum state analogous to the target probability distribution over vertices. This quantum state, when measured, gives a corresponding classical sample from the target distribution. We also give a second classical algorithm for sampling from probability distributions over graph vertices. This algorithm adds different self-loops to each vertex of the random walk. We show how to construct the quantum analogue of this algorithm. Finally, we show that we can embed this quantum analogue into our controlled quantum walk.","abstract_html":"We give a new quantum algorithm to sample from probability distributions over graph vertices quadratically faster than the optimal classical algorithm, which uses random walks with stopping rules. Efficient sampling is an important computational task used in simulations based on stochastic processes. This is the first quantum algorithm that achieves a quadratic speed-up for sampling from general probability distributions over graph vertices. Our algorithm generalizes the controlled quantum walk algorithm proposed by Dohotaru and Høyer in 2015. Our main technical innovation is to allow for multiple distinct controlled reflections. This allows us to generate the quantum state analogous to the target probability distribution over vertices. This quantum state, when measured, gives a corresponding classical sample from the target distribution. We also give a second classical algorithm for sampling from probability distributions over graph vertices. This algorithm adds different self-loops to each vertex of the random walk. We show how to construct the quantum analogue of this algorithm. Finally, we show that we can embed this quantum analogue into our controlled quantum walk.","abstract_has_math":false,"creators":["Bencivenga, Dante"],"institution":"Science","degree_name":"Master of Science (MSc)","degree_level":null,"degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":[],"advisors":["Høyer, Peter"],"committee_chairs":[],"committee_members":["Feder, David","Woelfel, Philipp"],"year":2020,"date_issued":"2020-10-26","date_published":"2020-10-26","updated_at":"2026-07-24T01:30:20Z","subjects":["Quantum Computing","Quantum Algorithm","Quantum Walk","Random Walk","Sampling","Controlled Quantum Walk","Quantum Hitting Time"],"languages":["English","en"],"rights":["University of Calgary graduate students retain copyright ownership and moral rights for their thesis. You may use this material in any way that is permitted by the Copyright Act or through licensing that has been assigned to the document. For uses that are not allowable under copyright legislation or licensing, you are required to seek permission."],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier.doi","label":"DOI","values":["http://dx.doi.org/10.11575/PRISM/39381"],"render_values":[{"text":"http://dx.doi.org/10.11575/PRISM/39381","href":"http://dx.doi.org/10.11575/PRISM/39381","code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/1880/114117","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Høyer, Peter"]},{"key":"dc:contributor.committeemember","label":"Committee Member","values":["Feder, David","Woelfel, Philipp"]},{"key":"dc:creator","label":"Author","values":["Bencivenga, Dante"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["Winter Conferral"]},{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2021-11-19T22:02:55Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2021-11-19T22:02:55Z"]},{"key":"dc:date.issued","label":"Date","values":["2020-10-26"]},{"key":"dc:publisher.institution","label":"Dc Publisher Institution","values":["University of Calgary"]},{"key":"dc:type","label":"Dc Type","values":["master thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Master of Science (MSc)"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Calgary"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Quantum Computing","Quantum Algorithm","Quantum Walk","Random Walk","Sampling","Controlled Quantum Walk","Quantum Hitting Time"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["English","en"]},{"key":"dc:rights","label":"Dc Rights","values":["University of Calgary graduate students retain copyright ownership and moral rights for their thesis. You may use this material in any way that is permitted by the Copyright Act or through licensing that has been assigned to the document. For uses that are not allowable under copyright legislation or licensing, you are required to seek permission."]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.doi","label":"DOI","values":["http://dx.doi.org/10.11575/PRISM/39381"]},{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/1880/114117"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["We give a new quantum algorithm to sample from probability distributions over graph vertices quadratically faster than the optimal classical algorithm, which uses random walks with stopping rules. Efficient sampling is an important computational task used in simulations based on stochastic processes. This is the first quantum algorithm that achieves a quadratic speed-up for sampling from general probability distributions over graph vertices. Our algorithm generalizes the controlled quantum walk algorithm proposed by Dohotaru and Høyer in 2015. Our main technical innovation is to allow for multiple distinct controlled reflections. This allows us to generate the quantum state analogous to the target probability distribution over vertices. This quantum state, when measured, gives a corresponding classical sample from the target distribution. We also give a second classical algorithm for sampling from probability distributions over graph vertices. This algorithm adds different self-loops to each vertex of the random walk. We show how to construct the quantum analogue of this algorithm. Finally, we show that we can embed this quantum analogue into our controlled quantum walk."]},{"key":"dc:title","label":"Title","values":["Sampling Using Controlled Quantum Walks"]}]}],"canonical_facts":{"dc:contributor.advisor":["Høyer, Peter"],"dc:contributor.committeemember":["Feder, David","Woelfel, Philipp"],"dc:creator":["Bencivenga, Dante"],"dc:date":["Winter Conferral"],"dc:date.accessioned":["2021-11-19T22:02:55Z"],"dc:date.available":["2021-11-19T22:02:55Z"],"dc:date.issued":["2020-10-26"],"dc:description.abstract":["We give a new quantum algorithm to sample from probability distributions over graph vertices quadratically faster than the optimal classical algorithm, which uses random walks with stopping rules. Efficient sampling is an important computational task used in simulations based on stochastic processes. This is the first quantum algorithm that achieves a quadratic speed-up for sampling from general probability distributions over graph vertices. Our algorithm generalizes the controlled quantum walk algorithm proposed by Dohotaru and Høyer in 2015. Our main technical innovation is to allow for multiple distinct controlled reflections. This allows us to generate the quantum state analogous to the target probability distribution over vertices. This quantum state, when measured, gives a corresponding classical sample from the target distribution. We also give a second classical algorithm for sampling from probability distributions over graph vertices. This algorithm adds different self-loops to each vertex of the random walk. We show how to construct the quantum analogue of this algorithm. Finally, we show that we can embed this quantum analogue into our controlled quantum walk."],"dc:identifier.doi":["http://dx.doi.org/10.11575/PRISM/39381"],"dc:identifier.uri":["http://hdl.handle.net/1880/114117"],"dc:language.iso":["English","en"],"dc:publisher.institution":["University of Calgary"],"dc:rights":["University of Calgary graduate students retain copyright ownership and moral rights for their thesis. You may use this material in any way that is permitted by the Copyright Act or through licensing that has been assigned to the document. For uses that are not allowable under copyright legislation or licensing, you are required to seek permission."],"dc:subject":["Quantum Computing","Quantum Algorithm","Quantum Walk","Random Walk","Sampling","Controlled Quantum Walk","Quantum Hitting Time"],"dc:title":["Sampling Using Controlled Quantum Walks"],"dc:type":["master thesis"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_name":["Master of Science (MSc)"],"thesis:institution_name":["University of Calgary"]},"updated_at":"2026-07-24T01:30:20Z"}