Inspiration

One of our primary goals when delving into the vast world of quantum computing was to create something meaningful. We wanted our code to give an output that, when applied, actually supports meaningful results and can lead to effective change in the future. After many mediocre ideas, we turned to the idea of fire station coverage. After a false fire alarm at our dorm room a couple weeks ago, we realized that it can take the fire department a hefty amount of time to arrive at an emergency depending upon the location of the station. The key to solving this is to make sure that you have optimal station placement to maximize your ability to reach people effectively.

Our Solution

Using a Hamiltonian based optimizer, our model takes into account the population of several neighborhoods and relates it to fire station accessibility. Through Qiskit quantum modeling, our code locates the optimal set of locations for a given amount of fire stations. As a result, we can determine the most effective locations for which to build each fire station.

A Hamiltonian Based Approach

The Hamiltonian of a system outputs the total energy of the system. By translating the cost function \(C(x)\) of our system to the Cost Hamiltonian \(H_C\), we can optimize the system using a Virtual Quantum Eigensolver (VQE) to the lowest energy states. Since we related this to our initial cost function, the lowest energy state corresponds to the configuration with the lowest cost, i.e. the most optimal one. By using this method, large cities with many possible locations for fire stations can be more efficiently mapped using qubits compared to typical classical computing.

The Challenges of Optimization

Aside from the natural learning curve inherent to exploring a new field, the primary challenge our model faced was the process of translating the cost function to our Cost Hamiltonian. Due to the existence of several summations and repeat products, converting a binary variable to a quantum object via Pauli Z gates proved tedious and challenging. Luckily, with some tricky python coding, we were able to create an efficient method of mapping a cost function of n variables to a Hamiltonian. Another difficult challenge was creating our ansatz such that all possible combinations of solutions were possible during optimization. Such led us down an exploration of XY gates and their effect on qubits.

Easy to Use Scalability

One of the major accomplishments of our model is that it easily scales to larger systems of neighborhoods and fire stations. We have built in quantity scaling, allowing user determination of neighborhood quantity and required fire station count. Users are able to explore multiple configurations while still receiving the optimal output. Furthermore, our process can be easily established to almost any system with binary cost function. Such examples include but are not limited to EEG Electrode Selection, Package Delivery Routing, and Dutch Auctions.

Our Thoughts

To us, the biggest takeaway is the power and use of a Hamiltonian. To be able to easily translate between classical and quantum systems in regard to optimization is game changing. Since quantum computing is best designed for large scale optimization outside of reasonable classical computation, to have a consistent way to translate from one to the other with a simple methodology is extremely beneficial.

What's Next

Our system showcases that it is possible to easily transfer classical optimization problems to quantum computing, however, the large-scale computational power needed for this to be beneficial does not exist yet. As a result, current classical algorithms will easily run faster than our model. However, our model shows that it is possible to use quantum models and that, when the resources do arrive, it can be easily implemented. For now, our goal is to continue to make our code more efficient and effective, working to better understand it in all its beauty.

Built With

  • aersimulator
  • hamiltonians
  • ibmquantum
  • python
  • qiskit
  • vqe
Share this project:

Updates

Submission history