Quantum search has emerged as one of the most promising fields in quantum computing.Stateof-the-art quantum search algorithms enable the search for specific elements in a distribution by monotonically increasing the d...Quantum search has emerged as one of the most promising fields in quantum computing.Stateof-the-art quantum search algorithms enable the search for specific elements in a distribution by monotonically increasing the density of these elements relative to the rest of the distribution.These kinds of algorithms demonstrate a theoretical quadratic speed-up on the number of queries compared to classical search algorithms in unstructured spaces.Unfortunately,the major part of the existing literature applies quantum search to problems whose size grows exponentially with the input size without exploiting any specific problem structure,rendering this kind of approach not exploitable in real industrial problems.In contrast,this work proposes exploiting specific constraints of an outage planning problem,consisting in setting outage dates of production units under specific fuel management constraints and resource constraints limiting the number of outages in parallel,to build an initial superposition of states with size almost quadratically increasing as a function of the problem size.This state space reduction,inspired by the quantum walk algorithm,constructs a state superposition corresponding to all paths in a state-graph,embedding spacing constraints between outages.Our numerical results on quantum emulators highlight the potential of the statespace reduction approach.In our simplified use case,the number of iterations required to reach a 90% probability of measuring a feasible solution is reduced by a factor between 2 and 4.More importantly,the squared ratio between the number of possible configurations and the number of valid solutions shifts from exponential to linear behavior,demonstrating that the quadratic speedup offered by Grover-based algorithms becomes sufficient in this setting.While these results are based on a simplified scenario and further investigation is needed to generalize them to large-scale industrial problems,they illustrate the promise of structure-aware initialization in significantly improving the efficiency of quantum search by focusing on a smaller,more relevant solution space.展开更多
文摘Quantum search has emerged as one of the most promising fields in quantum computing.Stateof-the-art quantum search algorithms enable the search for specific elements in a distribution by monotonically increasing the density of these elements relative to the rest of the distribution.These kinds of algorithms demonstrate a theoretical quadratic speed-up on the number of queries compared to classical search algorithms in unstructured spaces.Unfortunately,the major part of the existing literature applies quantum search to problems whose size grows exponentially with the input size without exploiting any specific problem structure,rendering this kind of approach not exploitable in real industrial problems.In contrast,this work proposes exploiting specific constraints of an outage planning problem,consisting in setting outage dates of production units under specific fuel management constraints and resource constraints limiting the number of outages in parallel,to build an initial superposition of states with size almost quadratically increasing as a function of the problem size.This state space reduction,inspired by the quantum walk algorithm,constructs a state superposition corresponding to all paths in a state-graph,embedding spacing constraints between outages.Our numerical results on quantum emulators highlight the potential of the statespace reduction approach.In our simplified use case,the number of iterations required to reach a 90% probability of measuring a feasible solution is reduced by a factor between 2 and 4.More importantly,the squared ratio between the number of possible configurations and the number of valid solutions shifts from exponential to linear behavior,demonstrating that the quadratic speedup offered by Grover-based algorithms becomes sufficient in this setting.While these results are based on a simplified scenario and further investigation is needed to generalize them to large-scale industrial problems,they illustrate the promise of structure-aware initialization in significantly improving the efficiency of quantum search by focusing on a smaller,more relevant solution space.
