.svg)
Why are there so many sorting algorithms?
Wikipedia lists 43 different sorting algorithms. Quick sort, Merge Sort, Shell sort, Bubble Sort, Pigeonhole sort, Spreadsort, Bead sort, Stooge sort, and many more.
Why so many?
Because different sorting algorithms are useful in different circumstances.
- Some (Bubble sort) are simple to implement, and thus useful for teaching.
- Some (Merge sort, Heap sort) have a relatively low limit on the worst-case number of operations they have to perform. If they need to sort N elements, they will never need more than O(N log N). Note: see here for a definition of O()
- Some (Insertion sort, Cube sort) have a low number of "best case" operations, meaning that they finish quickly if the list of already sorted. For N elements, their best case will be O(N)
- Some (Heap sort) need very little memory
- Some (Bead sort) only work with positive integers
- Some... well, you get the point.
An engineer that wants to use a sorting algorithm would do well to think about the characteristics of the data that needs to be sorted, the constraints of processor, the availability of parallel processors, and many other constraints. While some algorithms are more popular than others, there is no single algorithm that is best in all circumstances.
The same is true for quantum algorithms.
There is no single implementation of state preparation that's always best. Some use fewer qubits. Some are more accurate. Some have smaller depth. So the choice of the best state preparation depends on the system you are using but also on what else is going on: what else are you doing beyond state preparation. The best implementation is not just decided at the functional block level, but actually at the system level.
Even simple quantum adders could have multiple implementations. You could build a simple ripple adder, or you can perform quantum arithmetic with the Quantum Fourier Transform (QFT).
This is why the best frameworks for generating quantum circuits will provide multiple options - and perhaps make an optimal choice on their own - instead of forcing you to use a single hard-coded implementation every time.
Wikipedia lists 43 different sorting algorithms. Quick sort, Merge Sort, Shell sort, Bubble Sort, Pigeonhole sort, Spreadsort, Bead sort, Stooge sort, and many more.
Why so many?
Because different sorting algorithms are useful in different circumstances.
- Some (Bubble sort) are simple to implement, and thus useful for teaching.
- Some (Merge sort, Heap sort) have a relatively low limit on the worst-case number of operations they have to perform. If they need to sort N elements, they will never need more than O(N log N). Note: see here for a definition of O()
- Some (Insertion sort, Cube sort) have a low number of "best case" operations, meaning that they finish quickly if the list of already sorted. For N elements, their best case will be O(N)
- Some (Heap sort) need very little memory
- Some (Bead sort) only work with positive integers
- Some... well, you get the point.
An engineer that wants to use a sorting algorithm would do well to think about the characteristics of the data that needs to be sorted, the constraints of processor, the availability of parallel processors, and many other constraints. While some algorithms are more popular than others, there is no single algorithm that is best in all circumstances.
The same is true for quantum algorithms.
There is no single implementation of state preparation that's always best. Some use fewer qubits. Some are more accurate. Some have smaller depth. So the choice of the best state preparation depends on the system you are using but also on what else is going on: what else are you doing beyond state preparation. The best implementation is not just decided at the functional block level, but actually at the system level.
Even simple quantum adders could have multiple implementations. You could build a simple ripple adder, or you can perform quantum arithmetic with the Quantum Fourier Transform (QFT).
This is why the best frameworks for generating quantum circuits will provide multiple options - and perhaps make an optimal choice on their own - instead of forcing you to use a single hard-coded implementation every time.
About "The Qubit Guy's Podcast"
Hosted by The Qubit Guy (Yuval Boger, our Chief Marketing Officer), the podcast hosts thought leaders in quantum computing to discuss business and technical questions that impact the quantum computing ecosystem. Our guests provide interesting insights about quantum computer software and algorithm, quantum computer hardware, key applications for quantum computing, market studies of the quantum industry and more.
If you would like to suggest a guest for the podcast, please contact us.
