s2fieldsofstudy:
Computer Science
Physics

text:
Finding paths in tree graphs with a quantum walk

In this paper, we analyze the potential for new types of searches using the formalism of scattering random walks on Quantum Computers. Given a particular type of graph consisting of nodes and connections, a"Tree Maze", we would like to find a selected final node as quickly as possible, faster than any classical search algorithm. We show that this can be done using a quantum random walk, both exactly through numerical calculations as well as analytically using eigenvectors and eigenvalues of the quantum system.

A more recent application of quantum walks is in state transfer, where the objective is to use the quantum walk to transfer the particle from a starting vertex to a final vertex, with high probability. It was shown that using a coined quantum walk, a perfect state transfer can be achieved for a star graph and complete graph with selfloops [17], as well as analysis on a complete bipartite graph [18]. With the recent experimental realization of discrete-time walks [19][20][21][22][23][24], it is hoped that these and other quantum walk applications may some day soon be tested experimentally.
Similar to the premise of state transfers, it has been shown that it is possible to use a quantum walk to find a path between two marked vertices [25]. In that study, the graph consisted of M linked star graphs. Each star had N edges emanating from a central hub with each edge connected to an additional vertex, which was called an external vertex, to distinguish it from the hub vertex. The stars were arrayed in a line. The first and last stars each had a distinguished vertex, labelled START on the first star and FINISH on the last star. Each star was connected to its neighbor at one vertex, but it was not known which vertex on star j, 1 ≤ j ≤ N − 1, was connected to which vertex on star j + 1. A classical search would take of order O(M N ) steps to find the path between START and FINISH, while the quantum walk only took of order O(M √ N ) steps.
Here we want to extend the study of finding paths to tree graphs.

B. N-Tree Maze
The focus of this paper is to explore the possibility of using quantum walks as a means of searching complex mazes that can be represented as nodes and connections on a graph G. To do this, we explore its effectiveness on a specific type of graph, an N-Tree maze.
An N-Tree maze is illustrated in figure 1. From the viewpoint of a solver, the maze consists of junctions with N identical choices. Beyond each choice is another identical junction with N choices, and so on. The maze is characterized as M -layers deep, thus to correctly find the exit one must make M correct choices in succession. The figure below would be categorized as N =2, M =4. If an incorrect path is chosen at any point, it is impossible to know exactly where the mistake was made without backtracking and exhausting all possible paths. The goal of searching through these graphs is to locate the specified final node F. For this discussion, it is assumed that the location S, the starting node, is known. The location of F is unknown, but N and M are given.
The layout of this paper is as follows. In Section 2, we discuss how a classical computer searches through the maze, and introduce the formalism by which a quantum computer searches using a quantum walk. In Section 3, we discuss the resulting quantum system after implementing the quantum walk, and the way probabilities are distributed throughout the maze. In Section 4, we analyze the various ways one can use the quantum walk to search for F. In particular, we analyze the effectiveness of using the probability concentrated on the edges connected to F, versus using the probability concentrated along the entire path from S to F. In section 5, we derive an expression for the number of trials needed to find F with high probability. And lastly in Section 6, we provide approximate solutions to N-Tree mazes by studying the systems' eigenvalues and eigenstates. We conclude by numerically solving for a form for U(N, M ), the function that gives the number of steps need to prepare a maze of size N, M .

A. Classical Search Schemes
For a general maze that can be specified through nodes and connections (also referred to as vertices and edges) on a graph G, often times the best classical search algorithm is a "depth-first" or "breadth-first" search. The two techniques only differ in how they traverse the maze, but share the same underlying principles. The algorithms search recursively through the maze, where one "step" amounts to moving one node at a time and keeping a list of all connected nodes as well as ones previously visited.
If we turn our attention to N-Tree mazes, M layers deep, the search best suited for this maze geometry is a depth-first search. Since the general structure of the maze is known (no internal loops or irregularities) and only the location of F is unknown, the minimum number of steps to reach F is M, while the maximum is E, the total number of edges. E is equal to (N M +1 −1)/(N −1), thus the average number of steps needed is of the order O (N M ). The real merit of any quantum search algorithm will then be to do better than this scaling.
Once begun, the classical search will always find F, given enough time. The algorithm moves through the maze and checks all the end nodes in succession, each one with a probability of 1 N M . Figure 2 shows the probability of finding the correct final node as a function of steps, searching on a 'Binary Tree' (N =2), M =3. In this example there are 8 possible end nodes where F could be, thus each jump in the graph corresponds to the algorithm checking one of these nodes.

FIG. 2:
The probability of successfully locating F as a function of steps, using a classical depth-first search. Each time an end node is checked, the result is a spike in probability.
As the size of these tree mazes get larger, a linear approximation becomes more accurate. We will use these linear approximations to compare classical vs quantum algorithms, and their probabilities of finding the correct final node. On average, the algorithm must check 50 % of the final nodes before finding the correct one, thus the average number of steps needed is of the order O (N M ). The real merit of any quantum search algorithm will then be to do better than this scaling.

B. Quantum Search using a Random Walk
To compete with the classical depth-first search, we will use a scattering quantum walk algorithm on the same graph geometry. Using this formalism, the particle resides on the edges of the graph, and can be thought of as being scattered by the nodes. The Hilbert space H is spanned by 2E orthonormal states, two states per edge of the graph. In particular, suppose we have two nodes A and B connected by an edge. Then there is a state |A, B which represents the particle scattering into node B, coming from node A, and vice versa for state |B, A .
The scattering walk is a discrete-time quantum walk. The evolution of the system is given by a unitary operator U that advances the walk one time step. This U is obtained by combining the actions of local unitary operations, one for each vertex, which describe the scattering at their respective vertices. In particular, they relate the state entering the vertex at one time step to the state(s) leaving the vertex at the next time step. For a vertex connected to n edges, with n ≥ 3, the action of U is given by where 1 ≤ j ≤ n, and The constants t and r can be thought of as transmission and reflection coefficients, respectively. In the special case of end nodes, defined by a node with only 1 connection, t = 0 and r = e iθ . For these nodes, r can be any complex number of modulus one, but for our purposes we will only consider the cases where r is equal to either 1 or −1. Specifically, we let the final node F reflect with −1, while all other end nodes (including S) reflect with 1. Now having defined H and the evolution of the system, we must choose the initial state of the system. We start with an equal superposition of all states, reflecting the fact that we have no a priori knowledge of the location of F. The fact that U acts differently on F drives the quantum system into a nonuniform distribution of probabilities, which is then probed by making a measurement on the system.

III. QUANTUM WALK ON N-TREE MAZES
In this section we will present results of using a quantum walk on N-Tree mazes. We look at two significant features that arise: 1) The concentration of probability on the correct final node F, and 2) The concentration of probability on the all the states making up the path from S to F. These results are generated numerically. Later we will try to gain a better understanding of them by looking at eigenstates of U , also numerically, in section 6.
In both cases, we find a cyclic rise and fall in probabilities. Figure 3 shows an example of these trends. The location of these peaks (the number of unitary steps needed) increases with maze size, both N and M . We discuss this in detail in section 6, but for a rough sense of magnitude, one needs of the order O(N M 2 ) unitary steps to reach the peak in probability.

A.
Probability Concentration on F By letting the correct final node reflect with -1, and all other final nodes with +1, the result is peaks in probability where F is significantly more probable than any other final node. These peaks come in regular cycles, but only the first peak is ever considered in this discussion. For these first peaks, the table below shows the maximum probability of measuring F for various N and M values. As shown, the peak probability decreases as N and M get larger, which translates to more trials on average before finding F. However, since this decrease in probability gets smaller as the maze size increases, the effectiveness of using these probabilities for searches will still prove useful.

B. Probability Concentration on the Path
Looking at figure 4, we see that at the first peak, the probability that the particle making the walk is on one of the states connected to F is quite low. By contrast, figure 5 below reveals that the probability of finding the particle on one of the states connecting S to F (including the states connected to F) is quite high. This result was also shown in [25], where using the same type of quantum walk, nearly all of the probability in the system became concentrated along the path connecting a series of stars. For our N-Tree mazes, Figure 5 below shows the maximum probability of measuring a state along the correct path for various N and M values. When we focus our attention to the states connecting S to F, we find that the overall peak probability increases with larger N and M . Thus, as the size of the maze increases, it becomes more probable that a state along the correct path is measured. In numerical tests, this trend continued as N and M increase, with the path probability approaching 1 as N and M become very large.
If we look at the breakdown of the peak path probability, figure 6 shows an example of how the individual states each contribute. Most importantly, even with individual fluctuations, all the states along the path peak around the same time, giving rise to the overall shape depicted in figure 3. The curves that are all very closely clustered together near the top are the states closest to the final node F, while the curves corresponding to lower peak values are closer to S. So when a measurement is made at the moment of the peak path probability, we get a sort of blending of all the correct path state probabilities, slightly favoring states closer to F. This fact will become meaningful in the next section, when we analyze the use of the path probability as a means to search for F.

IV. COMPARING ALGORITHMS AND SPEEDS
Here we will lay out a few possible algorithm schemes that take advantage of the quantum system, and we compare their effectiveness in finding F. There are two main disadvantages that exclusively plague the quantum algorithms: 1) The system must run a pre-determined number of unitary steps before each measurement. 2) All measurements are probabilistic, so any measurements that fails to find F means that the entire quantum system must be prepared again. We will see that the most effective algorithms work to minimize these disadvantages.
For the quantum algorithm that will come later in this section, we will always be preparing our quantum systems for a peak path measurement. Let us define U(N, M ) as the function that gives us the prescribed number of unitary steps needed to prepare our quantum system for this peak path measurement, for any N and M . A complete form fot this function will be given in section 6. For now, we would like to use U(N, M ) as a metric for defining "average speed", which we shall use throughout this paper.
Rather than expressing speed in terms of steps, let us define average speed (for both classical and quantum) as: the ratio of the average number of steps needed to find F to U(N, M ). Using this definition, for a given maze of size N and M , the fastest a quantum algorithm can find F is 1. This is because we are always constrained to prepare our quantum system, for a peak measurement, at least once. Thus the theoretical limit of 1 would then correspond to a 100% success rate of finding F on the first measurement.

A. Classical Search Speed
The classical search algorithm works like opening doors, checking each final node to see if it's the correct door, and if not moving onto the next one. Initially, all final nodes have equal probability of being correct, with each wrong node reducing the sample space by 1. Thus, the average speed of the algorithm is determined by the average number of nodes we need to check.
As depicted in figure 2, a linear approximation is sufficient, especially for larger mazes. Equation 3 gives the linear function corresponding to the probability of success as a function of steps.
By setting P(steps) = 1 2 , we get the average number of steps needed for a classical search: Steps avg = E 2 . Thus, the classical depth-first search algorithm needs to, on average, step through roughly half the maze before finding the correct final node, which scales like O(N M ) B. Searching for F Directly Suppose we are only interested in searching for the correct final node, discarding all other measurement results. This method is analogous to the Grover search, however, here our chance of success decreases with the size of the maze. As a result, larger mazes will on average expect more failures. Compounded with the fact that larger mazes require more unitary steps to prepare, this type of search suffers drastically from both disadvantages previously mentioned. Nevertheless, we shall see that searching for F directly does indeed provide a speedup over the classical search.
Provided that we know when to probe the quantum system for the maximum probability of measuring F, say given by U F (N, M ), this type of search is analogous to rolling dice. We prepare and probe the quantum system over and over until F is found. If we let p be the probability of measuring F, then our probability of success as a function of trials, T , is of the form given in equation 4. And the average number of trials is given by equation 5.
If we take the number of trials, and multiply by the number of unitary steps it takes to prepare the quantum system, this gives us our relation between success probabilities and steps. Figure 7 shows a comparison of these probabilities for the case N =2, M =15. Since the two types of probabilities are very different, opening doors versus rolling a dice, one must be cautious in comparing the two. Figure 7 suggests that the quantum search is favorable in practically all regions, but when put into practice we want to avoid falling for a Monte Carlo fallacy, thinking the quantum search is faster than it actually is. For this reason, the average number of steps needed to find F for the two searches are marked along the x-axis. In terms of average speed, as defined earlier, we take these average numbers of steps and divide them by U F (N, M ). We then find that the classical search has an average speed of 21.4 while the quantum search is 11.2, thus resulting in a speedup of 1.9. For the quantum search, the average speed can also be viewed as the average number of times the system will need to be prepared. Figure 8 below shows the speedups (ratio of classical to quantum average speeds) for N =2, for various M . Thus, we do indeed get a speedup by imitating the Grover ideology and searching for F directly. We find that the speedup increases exponentially with the size of the maze. Next, we will show that we can do much better by utilizing what else the quantum system has to offer, specifically the huge peak probability of the correct path.

C. Moving Through The Maze
The major shortcoming of the pervious search scheme is the amount of wasted steps. Every time a measurement doesn't yield the correct final node, it is discarded. Rather than simply starting over, it would be better if we could extract some kind of meaningful information from these "failed" measurements.
This is preciously what our next quantum algorithm proposes to do, use the information from previous measurements to guide future ones. To do this, we probe the system when measuring a state along the correct path has the highest probability, rather than maximizing for measuring F. This is because we are anticipating that most measurements will not find F, so instead we will hedge our bets towards the measurement being along the correct path.
Since we will choose to probe at a different time, we need to first make sure that we aren't sacrificing our search for F (which is the ultimate goal) by probing when the path is most probable. Figure 9 shows a comparison of the probability of measuring F, when the system is prepared for maximal F probability versus maximal path probability, for N =2. At lower M 's, particularly 5 and 6, we see a significant decrease in probability for measuring F. However, as the size of the maze increases, we get virtually no loss in probability for F. Thus, for larger mazes, we do not sacrifice anything by probing for a peak path measurement. Now in order to make use of the following algorithm scheme, it is assumed that we have flexible control over our quantum system. Namely, we have the ability to turn nodes "on" or "off". Specifically, nodes that previously had multiple connections when "on", now act as end nodes with only one connection when "off". Figure  10 below shows an example. Suppose the edge marked with a star was the result of the first measurement, the node connected to that edge, closer to S, is then turned "off." The result is that all the subsequent nodes behind it are "frozen out," illustrated by the grey dash lines. The remaining edges and nodes form a new graph G and Hilbert space H.
Changing the geometry of the system is accompanied with a change to the unitary operator U, to properly operate on the new system H. In practice, we will only ever tweak our system at one location, after a measurement has been made. But doing so will always result in freezing out a large section of the initial maze.
FIG. 10: Following a measurement (marked by the star), we then turn a single node "off" and consequently freeze out edges and nodes behind it (illustrated as grey-dashed lines). These frozen out edges and nodes no longer affect the active quantum system (illustrated as black-solid lines), and are no longer in the Hilbert space H or Unitary operator. Now we are equipped to discuss the core idea proposed by this paper: "moving" through the quantum system. By movement, we mean changing our quantum system after we make a measurement, to reflect the algorithm's scheme for searching through the maze. As shown in figure 10, the result of a measurement dictates which nodes we turn off, or in other words where we "move" through the maze. In example given, the measurement results in a movement from an M =4 maze, down to M =2. From there, the process is repeated until one of two outcomes occurs: the correct final node F is measured, or an incorrect final node is measured. In the latter case, we must start over from the very beginning, turning on all nodes and preparing the original full maze.
The benefits of moving from an M to a smaller M ' (where M ' < M ) layered maze are as follows: 1) Each preparation of the system will cost fewer unitary steps to reach the peak probability 2) Each measurement will have a higher probability of measuring the correct final node (except for a few cases at lower M 's). Thus, if one can successfully move through the maze in increments towards the correct final node, both of the main disadvantages of the quantum algorithm are minimized simultaneously.
However, the trade-off for movement is the potential new risk of measurement leading to an incorrect step. Any algorithm that utilizes movement through the maze must also have a means of correcting for a movement in a wrong direction, otherwise they could become permanently stuck. We will refer to such an event as stepping into a "dead tree," and analyze its impact on the algorithm next.

D. Moving Into a dead tree
Let us discuss the event in which a measurement results in a movement in the wrong direction, into a dead tree. Based on the probabilities shown in figure 5, such an even has a small occurrence rate, but is nevertheless worth analyzing. Our interest is how quickly the algorithm finds a final node, and effectively exits the dead tree by resetting the problem back to the initial maze.
When a measurement yields a state that is not along the correct path, the solver has no way of knowing. Thus, following the protocol of the algorithm, one would move to the smaller maze and apply the prescribed number of unitary operations based on U(N, M ). However, since the special node F is no longer in the system, the result of the quantum walk leaves all the states equally probable. But since the structure of each maze is heavily weighted by states closer to the end (refer to figure 1), having all the states be equally probable is a huge advantage for measuring a final node or ones closest to a final node.
As it turns out, the overall loss in speed for misstepping is very negligible. Figure 11 shows the average speed for which the algorithm exits a dead tree, for N =2. We can see that as M becomes larger, the average number of wasted steps approaches U(N, M ). Because of this, the risk of dead trees slowing down the search algorithm becomes very minimal. In addition, this slowdown of approximately U(N, M ) steps occurs based on the size of the maze at the measurement, which in most cases is much smaller than the initial maze size. The largest cost in speed from a misstep actually occurs after the dead tree, when the initial maze, which has the largest U(N, M ), must be prepared again.

E. Results for Following the Measurement Algorithm
Recall from figure 6 that states closer to the correct final node, along the path, have slightly larger peak probabilities. Thus, when a state along the path is measured, the resulting layer is on average over half the distance to the final node. After which, each successive measurement does the same. Combine this style of movement with the fact that the maze sizes and U(N,M) scale exponentially, and the result is a powerful searching algorithm. Figure 12 shows the average speed of this algorithm in finding F, as well as the classical and searching for F directly algorithms. The results show that the movement algorithm outperforms all previous searches. Most notably, as the size of the maze increases, its speed slowly trends toward 1, the theoretical limit. In addition, the fact that the speeds are under 2 means that on average the algorithm finds the correct final node without ever making a misstep. Thus we see the true strength of relying on path probabilities to help guide our quantum searches.
In summary, the quantum algorithm that makes use of movement, and by extension avoids wasting information, outperforms those which don't. In quantum systems where a projective measurement completely collapses the wave function, it is ideal if one can use the information gained from prior experiments to help dictate future ones. For the movement algorithm, the only instances where a measurement yields no information are from measuring S, or measuring a wrong final node.
Whether or not any useful information can be extracted when an incorrect final node is measured, we do not know. We will leave this as an open question for possible future work, and next turn our attention towards some analytical solutions for N-Tree mazes.

V. NUMBER OF TRIALS
Let us examine how many trials the movement algorithm will need to find F. In an N -Tree maze, which is M layers deep, the correct path from S to F has M + 1 edges. We will label them with the coordinate x, where 1 ≤ x ≤ M + 1. The edge connected to S is x = 1, x = 2 is the next edge on the correct path, and x = M + 1 is the edge connected to F. We shall assume that the probability of the particle being on the correct path is p. This probability is close to one, and we will assume that it is independent of the size of the tree, which is a reasonable approximation for all but the smallest trees. We begin by finding the probability of a measurement sequence x 1 , x 2 , . . . , x n , where x 1 ≤ x 2 ≤ . . . x n , because when we find x j , we turn off the tree below this point .
Now consider the sum f (n, h) = N k=0 h k /k!, for h > 0. The terms in the sum initially increase as n increases, reaching a maximum when n is the greatest integer less than h. After that, they decrease. This suggests that if we choose n to be several times h, then the sum will be approximately equal to e h . In more detail, using the Stirling approximation, k! ≥ k k e −k , so assuming (he/n) < 1. If we choose n = rhe, then the bound is (1/r) rhe [r/(r − 1)]. So for he of order one, we can choose an r of] order one that will make the above sum small and set f (n, h) e h . Therefore, in Eq. (11), choosing z to be of the order p ln[(M + 2)/2], we have Consequently, we will need of the order p ln[(M + 2)/2] trials to find F with high probability.

VI. FINDING EIGENVALUES AND EIGENVECTORS
We have now shown how one can effectively use the path probabilities to find F more quickly (section 4), as well as how the movement algorithm leads to fewer trials need (section 5). Returning to the final point made in the Follow the Measurement section, for larger mazes the average number of steps needed to solve the maze approached the limit of U(N, M ). These results were found numerically, using the exact maximum path probability. But in general for any N-Tree maze, of any size, we would like some form for U(N, M ) that we can use.
In order to do so, we are interested in the eigenvectors and eigenvalues of the operator U , which advances the walk one step. This operator acts on a space of dimension 2E, but we can reduce this by using symmetry. Since we start from an initial state of the system in which all edges have the same amplitude, and we are interested only in later states of the system that can be reached from this initial state by the action of U , there will be some edges that always will have the same amplitude. This means that we only need to consider an equal superposition of the corresponding edge states, thereby reducing the dimension of the system. For example, in the tree in Fig.1, the two edges to the left of F will always have the same amplitude, and the four edges to the right of F will have the same amplitude. In both cases, we can replace multiple edges with a single effective edge. Doing so in an N-Tree maze, with M layers, allows us to consider a subspace of dimension (M + 1)(M + 2)/2. From here, we let a computer to find the eigenvectors and eigenvalues of the matrix of U expressed in the basis of effective edge states.

A. Eigenvector and Eigenvalue Characteristics.
When we let a computer solve for the eigenvalues and eigenvectors, it is found that everything comes in pairs. Specifically: 1) All eigenvalues come in pairs of complex conjugates.
2) All eigenvectors come in pairs, where the values in each vector come in corresponding complex conjugates. 3 This is a result of the fact that in the basis we are using, the matrix elements of U are real. This implies that the coefficients in the characteristic equation of the matrix are real, hence point 1). For point 2), note that if U |u i = λ|u i , then since U is represented by a real matrix, taking the complex conjugate of both sides gives us that |u * i is the eigenvector corresponding to λ * . Point 3) follows from the fact that the components of |Ψ init are real.
Letting λ i and |u i be the eigenvalues and eigenvectors of of the matrix U , we can represent the evolution of our system: where β i is the overlap of the eigenvector with the initial state Since the dimensions of the matrix corresponding to U can be quite large as M gets large, one would hope that only a handful of the βs are dominant, so that smaller terms can be dropped. This indeed turns out to be the case, as all of the β's are small enough to be ignored except for two (a corresponding pair of complex conjugates).
Keeping only the largest pair of β's and dropping all other terms, our approximate solution becomes: where e iθ λ is equivalent to the eigenvalue λ i , expressed in polar form. Now suppose we are interested in the behavior of a particular state in our original basis. Using the result from equation 16, we can reconstruct a given state, say |Φ , as follow: Let z φ = Φ|u , and let W φ (n) be the amplitude of state |Φ after n unitary steps, that is W φ (n) = Φ|U n |Ψ initial . Then we have If we rewrite β and z φ in polar form: = |β| · |z φ | · (e i(θ β +θz+θ λ n) + e −i(θ β +θz+θ λ n) ) = |β| · |z φ | · 2cos(θ β + θ z + θ λ n) (18) Thus, we get exactly the cyclic form we found numerically. By using the two dominant β's, we get the result of equation 18, which is that the amplitude of each state behaves sinusoidally as a function of unitary steps. Each edge state can be written as a cosine, with an initial angle of θ β + θ z , that increases by θ λ n after n steps.
Equation 18 above is general for all of the states in the system. However, we are primarily interested in the states that make up the correct path from S to F, say |α . For these states, a more appropriate representation will be: This is because for the states along the path, we find numerically that the quantity [θ β + θ z ] is near -π 2 . As a result, the states along the path behave like a sin function, reaching their peak amplitude when n is O( π 2θ λ ), offset just slightly by the small initial angle [θ β + θ z + π 2 ]. In addition to producing the observed sinusoidal nature, this approximation also tells us that all the states along the path should peak around the same time, which we indeed see. Figure 13 below shows a comparison of the approximation given in equation 19 versus the true value found numerically, as a function of unitary steps. As we can see, for a relatively small maze, the approximation is very close to the true value. For larger N and M values, the approximation becomes even better.

B.
Extracting Information for Higher Trends Using the approximation from the previous section, our real interest is to learn the form of U(N, M ), the function that tells us the required number of unitary steps for a peak path probability. With U(N, M ) in hand, we can extend the search potential of the previously laid out algorithms to any sized maze.
To get U(N, M ), we are going to use the eigenangles θ λ from the previous section. We will first get the function (N, M ), which gives the eigenangle θ λ corresponding to the most dominant β's, for any N and M . With the eigenangles (N, M ), we can then use the approximation in equation 19 to find the peak probability.
When a 3D plot is made of the (N, M ), with N and M on the x and y axes and the value of θ λ on the z, we find an exponentially decreasing function in both N and M . Looking at the 3D plot in slices for when we set M to a constant value, we can see recognizable trends for θ λ as a function of just N . These trends are of the form y = Ax B , where A and B are constants, and are plotted below in figure 14.
Note that (N, M ) here is in degrees. Using the best-fit solutions, shown in figure 14, we can analyze the forms for A(M ) and B(M ). Doing so reveals: where α, β, ρ, and γ are all constants. So we find that A(M ) also takes the form of a power function, while B(M ) is linear.
Putting everything together, we now have our approximate form for (N, M ), and more importantly U(N, M ): where α ≈ 47.87 β ≈ −.551 ρ ≈ .077 γ ≈ −.498 (23) These constants are all found numerically, using regression fitting. Their exact values may vary slightly by using larger sets of data to generate the regression fits. However, the values provided were generated using N and M up to 15. When tested to see if they reproduce the same peak path probabilities found numerically earlier, they do indeed produce the same peak probabilities, typically within 1-2% of the exact peak.

C. Final Remarks
In conclusion, we have found an approximate form for U(N, M ) through analytical results. Using the regression constants from equation 23, we see that the quantum system peaks around the order O(M .55 N .5M ). Comparing this to the classical speed O(N M ), we see a Grover-like speedup.
But this speedup is only possible by utilizing the "Follow the Measurement" algorithm, which provides us the fastest means of finding F. Specifically, as shown in figure 12, the jumping algorithm provides us with an average solving speed that is a small multiple of U(N, M ), roughly 1.5 times for mazes we studied. For larger mazes the ln M factor from Section V should manifest itself. However, multiplying U(N, M ) by ln M provides only an upper bound on the number of steps in the quantum algorithm, because it does not take into account that the size of the trees decreases as we jump up the path. For this reason, we can truly compare the two solving speeds, and say that the quantum walk provides a definitive speedup over the classical one. The number of steps in the quantum algorithm has an upper bound of the order O(M .55 N .5M ln M ). while the number of steps in the classical algorithm is O(N M ).

VII. CONCLUSION
We have developed a modification of the Grover search, where the probability accumulates on a path instead of on a marked vertex. However, when faced with the task of finding a special vertex, hidden in the deepest layer of an N-Tree maze, we have shown that making use of the probabilities of the states leading to the special vertex results in the fastest search. In particular, to capitalize on the system's high density of probability along the correct path, it is necessary incorporate changing the graph, which we called "movement," into the quantum algorithm. The ability to "mov" while searching for the special vertex, is analogous to the core element of the classical search.
Our efforts were focused solely on N-Tree mazes due to their high symmetry, and resulting high peak path probabilities. We would like to note that in addition to only F reflecting with -1, we also examined the case where both S and F reflect with -1, but found that letting S be a special vertex results in a less than ideal probability distributions for searches.
It was shown analytically that using the movement algorithm to search for F, one needs on average fewer trials to find F. In addition, by using computational tools to examine the eigenvalues and eigenstates of the various mazes' quantum systems, we provided an equation that reveals the underlying sinusoidal nature of the timebehavior of the system, to very close approximation. And by using these approximations, we were able to produce an approximate form to U(N, M ). Using U(N, M ) along with the average speeds found numerically in section 4, we have ultimately shown that the average solving speed of the quantum algorithm utilizing movement has an upper bound of the order O(M .55 N .5M ln M ), a speedup over the classical speed of O(N M ).


Insights on Research Techniques towards Cost Estimation in Software Design

Received Feb 16, 2017 Revised May 15, 2017 Accepted Aug 11, 2017 Software cost estimation is of the most challenging task in project management in order to ensuring smoother development operation and target achievement. There has been evolution of various standards tools and techniques for cost estimation practiced in the industry at present times. However, it was never investigated about the overall picturization of effectiveness of such techniques till date. This paper initiates its contribution by presenting taxonomies of conventional cost-estimation techniques and then investigates the research trends towards frequently addressed problems in it. The paper also reviews the existing techniques in well-structured manner in order to highlight the problems addressed, techniques used, advantages associated and limitation explored from literatures. Finally, we also brief the explored open research issues as an added contribution to this manuscript.

INTRODUCTION
Software development cycle plays a significant role in project management that directly impacts the productivity [1]. Normally, the process of software development involves longer duration and it suffers from certain paranoia of uncertainty [2][3]. The root cause of such uncertainty could be requirement volatility [4], defective project guidelines [5], skill gap [6], and wrong project planning [7]. An inappropriate project planning can lead to significant loss of resources with respect to time, money, and effort [8]. The prime stepping stone of success in project planning is to estimate the cost involved in the software project development. Therefore, we can define software cost estimation as the mechanism that performs forecasting the original and cumulative cost required to complete the software project on a tentative time in presence of all resources and constraints [9][10]. It is assumed to be highly complexities for many industries as cost involvement differs for different project and there are numerous factors that affect it. In this process, functional size matters the most as it is responsible for computing size of the software that is considered as the core input for majority of the modeling. One of the examples of such standard method is Common Software Measurement International Consortium (COSMIC) that is certified by ISO/IEX 19761:2011 [11]. Another essential indicator of the cost involvement is the development effort [12] that can be defined as effective amount of time used for developing the software project in progressive order. Since last decade, there has been evolution of various such mechanisms; however, none of the single mechanism can be said to 100% full proof for cost estimation [13]. Another indicator of the cost factor is line-of-code which is universally considered as the best metric to estimate cost of software development [14]. After the software is build, it is also required to be properly tested that could be done both by manual and by automated testing  [15]. There is also a cost involvement even in testing phase too and hence comprehensive testing mechanism that consumes more time and more resources are now fading slowly from the industry. According to the article presented by Smitte et al. [16], there are many reputed organization who has already initiated steps towards saving cost of software development. Irrespective of the type of work (complex software projects, test automation, remote support work, agile projects, etc), it is feasible for saving the cost provided an effective and error free modeling of cost estimation in software projects do exists.
However, there is a difference between the hype and reality. At present, there are quite a few standard techniques e.g. Constructive Cost Modeling (COCOMO) that is found exercised by various researchers for cost estimation and effort estimation. One of the biggest impediments towards modeling cost estimation techniques is to ensure accuracy in prediction rate. In order to perform prediction, the software modeling will be highly required to possess certain heuristic information [11]. In such cases, the model will be required to have access to higher number of heuristic organizational data and then its accuracy will be highly dependent on the dimension of heuristics. In other way, it can provide cost estimation but at the cost of organization resources. Hence, there are various experts who still believe that cost-estimation modeling is actually in its nascent stage and it will be quite necessary to perform re-investigation taking prominent cases of software development.
This paper discusses about the existing system, their effectiveness, limitation, in order to derive the open issues in software cost estimation. Section 1.2 discusses about the standard classification of the software cost estimation techniques in brief followed by discussion of research trends towards addressing research problem in Section 1.3. Section 2 elaborates about the existing research techniques on multiple problems highlights their advantages and limitation. Discussion of open research issues is carried out in Section 3 followed by conclusion in Section 4.

Background
Before, briefing the taxonomies of the existing software cost estimation techniques from research viewpoint, it is essential to understand certain brief detailing of it. Majority of the existing models visualizes the process of cost estimation as the function that is capable of performing computation from a evaluated cost drivers for an effective analysis [17]. The existing research work considers software requirement as the prominent cost driver. At present, there are various techniques of cost estimation techniques that can be seen from Figure 1. Basically, there are two different classified approaches i.e. algorithmic approach and nonalgorithmic approach.
Algorithmic techniques are those that adopt mathematical approach where the frequently used inputs for such approaches are function point, line of codes, etc. Basically, there are three forms of algorithmic approach viz. i) Putnam's Model, ii) Constructive Cost Model, and iii) Function Point Analysis. Putnam's model performs computation of size of software using environment factor, lines of code, dispatching time of software, and build up factor of manpower. Unfortunately this model doesn't consider various potential factors of development lifecycle [18]. The second approach i.e. constructive cost model is frequently used by various researchers and is again classified into further three forms i.e. i) fundamental model, ii) intermediate model, and iii) detailed model. The prime reason for its higher adoption is its simple technique to estimate cost and its wide adoption within the industry [19]. But it also suffers from various problems e.g. nonapplicability on smaller projects, estimation failures. The third algorithmic approach is Function Point Analysis that is used to measure the number of functional points available in the software projects. The prime factors in Function Point Analysis are interface file (external), logical file (internal), and varied enquiries. The interesting point of Functional Point Analysis is that it is independent from tools, language, or any specific implementation strategy. However, the pitfall of Functional Point Analysis is its manual operational technique [20]. On the other hand, non-algorithmic approaches are basically classified into 6 types (based on frequent research techniques) viz. i) top-down based, ii) Expert Judgment based, iii) Bottom-based, iv) Analogy Based, v) Artificial Neural Network (ANN), and vi) Fuzzy Logic. In top-down based approach, the global charecteristics are used for computing total cost and emphasizes more on integration. The limitation of this approach is its non-consideration of low-level problems leading to cost increment [21]. In Expert Judgment based approach, an expert's opinion is considered that is good for cases with restricted access to data. It can be used for predicting the influence on cost due to change of any underlying technologies [22]. In bottom-up based approach, the overall cost is estimated only after deriving cost of each components involved in software design. The stability of the technique is quite high but it ignores integration, documentation, etc [21]. The analogy-based approach is used for determining the parameters of existing software project as well as it also explores the equivalent old project whose parameters matches with the current project. The significant advantage of using analogy-based approach is supportability of estimator experience for assisting in enhanced cost estimation. Unfortunately, this approach is not applicable for all the software projects [23]. Both artificial neural networks as well as fuzzy logic are soft computing techniques where the former uses historical data and latter uses membership function. Although ANN offers consistency in cost estimation process buts it has maximum dependencies of training data to ensure accuracy [24]. Similarly, adoption of fuzzy logic based approach has the advantage of zero dependencies over training as well as it also offer comprehensive trustworthy cost estimation. However, even the fuzzy-logic based approach also suffers from pitfalls i.e. it offers computational complexities in many cases and moreover the accuracy completely depends on the type of the Ruleset being designed for this purpose of cost estimation [25]. Hence, it can be said that irrespective of the presence of various conventional software cost estimation techniques, there is less effective cost estimation technique for a large scale and dynamic software development process.  Figure 1. Taxonomies of existing software cost-estimation approaches

The Problem
This section highlights the statistics of varied number of research papers published in IEEE XPlore during duration from 2010 to till date pertaining to the problems associated with software cost estimation techniques. We reviewed the most commonly addresses problems in cost estimation techniques and graphically highlighted the current progress in it. The number of recent journals towards software cost estimation is found to be less than 50 (Figure 2), which is very less in number compared to other research problems in software modeling or engineering. The availability of relevant papers is quite less. Similar problem do existing in research towards effort estimation where only less than 25 journals are found till date ( Figure 3). The trend is much reduced for fault prediction in cost estimation ( Figure 4) as there are only 9 journals associated with this problem. Apart from this, we also investigated about the trends towards other usage of other approaches of cost estimation e.g. expert judgment, analogy-based, Putnam's model, Functional Point Analysis, COCOMO, etc. A closer look into the research trend in Figure 5 shows that Functional Point Analysis as well as COCOMO model is the most adopted techniques by various researchers till date. The proportion of the research papers using Functional Point Analysis is found to be comparatively higher than conventional COCOMO model. However, the matter of illusion is that usage of Functional Point Analysis was not adopted specifically for cost estimation problems in software and hence the relevancy rate of using Functional point analysis is quite low. Similarly, we find that although many research papers doesn't highlights COCOMO in the preliminary section of their papers, but we find that majority (say 95%) of the researchers have adopted COCOMO model in the implementation of their approaches. Hence, the present research trend can be said to use COCOMO model with higher relevancy factor compared to usage and adoption of other conventional techniques of cost estimation.

EXISTING RESEARCH TECHNIQUES
This section discusses about the existing research techniques towards cost estimation process in the industry. As there is so much varied process of investigating the cost factor by various researchers, the discussion is carried out for the frequently used computation techniques of cost factor in the software development process. We discuss only the recent research manuscript published in the duration of 2010-till date in this regards.

General Cost Estimation Techniques
From industry viewpoint, every sector has its own kind of criterion of measuring the total number of resources involved in the process of software development. In this regards, the adoption of Functional Point Analysis can be considered as highly standard and practical one as its adoption was found in many existing corporates and firms [26]. Basically, it is one of the mechanisms to perform quantification of the active functions that are used for designing the software and it retains higher significance. But although the usage of Functional Point Analysis started back in 1979 in IBM, it suffers certain pitfalls too that are investigated by the research community. Some of the significant pitfalls are i) inconsistent outcomes, ii) mismatched points during analysis, etc. A discussion about techniques for enhancing Functional Point Analysis was presented by Junior et al. [27]. It was seen that there are various forms of enhancement being carried out towards improving the accuracy of Functional Point Analysis e.g. Fuzzy logic, Artificial Neural Network, Statistical Regression, Genetic Algorithm, interpolation technique, etc. However, according to the analysis carried out by author majority of the existing techniques do still possess certain pitfalls e.g. no clear cut solution to countermeasure existing problems, higher complexity, dependencies on current version, etc. Another standard investigation towards software cost estimation was carried out by Mittas and Angelis [28]. A statistical modeling approach has been used for investigating different forms of existing models of cost estimation. Further, a clustering mechanism was applied for unique groups. The authors have performed the experiments using datasets for measuring accuracy followed by a ranking process to understand the most elite outcome. The authors have carried out Scott-Knott test over 11 standard models to find better predictive accuracy. The cost factor of the software projects also depends on the functional size of the code. It becomes quite a significant task when it comes to embedded system design as various units of embedded system e.g. memory is significantly affected by the control unit. Study in such direction was carried out by Lind and Heldal et al. [29] by presenting a standard mechanism for estimating embedded code size called as COSMIC approach. In order to extract the precise outcomes of the study, both functional sizes as well as size of software code were subjected to correlational analysis to find that they are higher correlated. Statistical analysis was applied for this purpose. The study outcome states that there are certain prominent factors that potentially affect the estimation process e.g. consistency of the contents, clear visualization of functional domain, superior requirement quality, and precise historical data. Not only in embedded system and design, similar problems do exists in fourth generation language. The degree of complexity towards fourth generation language is quite higher and this problem is investigated by Zia et al. [30]. The technique has used empirical data on the basis of the standard specification of COCOMO II model. The study outcome has been tested using multiple tools e.g. Visual Basic, VB.Net, VC# in order to compute both actual and forecasted effort to find higher accuracy. The significant studies towards general cost estimation is quite less in terms of number of journals. Although, few significant conference manuscripts have equally contributed to share certain novel ideas towards enhancing cost estimation techniques in software design. Most recently, Hihn et al. [31] have presented a technique that can estimate cost for National Aeronautics and Space Administration (NASA) based repository data. The technique also emphasizes on potential software metric e.g. logical lines of code with varied system parameters. Using multiple mission types of space objects (earth orbiter, observatory, deep space, etc), statistical measures were applied on the basis of standard COCOMO-II specification. The technique uses analogy-based approach with various inputs of levels of inheritance, size of software, types of elements, types of mission, etc and then spectral clustering is applied for computing effort. Similar form of celestial case study was also seen in the work carried out by Cannon and Burlet [32]. The study mainly develops a prototype of flight software using C language and observation was made for time variability, composition, and density over the moon surface. The author computed cost of this software model using extrapolation approach, COCOMO using agile methodologies using source line of code. These approaches have used the standard data from the space centers and can be considered as best initiative towards cost computing models using space related data. Another unique optimization-based technique of using bio-inspired approach was seen in the work of Garg and Gupta [33]. The authors addressed the problem of accuracy pertaining to usage of agile methodologies. The problems of attribute dimensions have been minimized using Principle Component Analysis followed by identification of prominent factor with higher correlation on software design cost. The study outcome is completely independent of historical data or any form of other information. The study has evaluated coefficient value of various test components e.g. size of team, complexity involved in projects, type of application, total functional points, platform used in  [34]. The author has applies Tabu search algorithm as well as genetic algorithm for this purpose. The technique uses NASA-related dataset along with COCOMO model to find reduced error in outcomes. Similar author has also applied Artificial Bee Colony along with genetic algorithm [35]. Adoption of Fuzzy Logic was seen in the work of Idri and Zahi [36] considering the dataset of web software. Liu et al. [37] have also used Particle Swarm Optimization in order to increase the accuracy of cost estimation for analogy based approach. Uniquely, the author considers a factor called as Non-Orthogonal Space Distance for estimating the similarity measures of the project. Sarno et al. [38] have used neural network for similar cause. Enhancement of analogy-based approach was seen in the study of Phannachitta et al. [39] using probability-based computation of distance function for cost computation.

Effort Estimation Technique
Effort estimation is the direct functional task to be carried out towards majority of the costestimation model till date. Although, there are various tools and technique to compute effort factor within an industry, but still there are certain open challenges towards implementing it e.g. inferior knowledge management, non-adaptability on standard estimation techniques, tool-related problems, negligence of project performance parameters [40]. Various challenges pertaining to the techniques of effort estimation at present are found to be human resources, governance, tools, and processes. At present, there is no such model or framework that overall addresses such problems jointly. Most recently, there is investigation towards effort estimation in software design in early stages for better consideration of probable cost involved within this. One such technique has been presented by Satapathy et al. [41], where the authors have applied frequently used machine learning approach known as random forest. The technique uses random forest for optimizing the accuracy in the predictive outcome. The study also considers various forms of the complexity factors e.g. portability, changeability, concurrency, efficiency of end user, code reusability, security features etc. The authors have also performs analysis over the error, proximities, complexities, and outliers. The study IJECE ISSN: 2088-8708 

Insights on Research Techniques towards Cost Estimation in Software Design (Praveen Naik)
2889 outcome was assessed using standard performance parameters e.g. mean squared errors, prediction accuracy, mean magnitude of relative error. Study towards development efforts and its estimation techniques have been also presented by Bardsiri et al. [42] towards the aim of enhancing the accuracy level. The authors have applied jointly multiple techniques e.g. analogy-based techniques, fuzzy logic, and neural network. The study outcome shows impressive percentage of prediction accuracy. It was observed that much of the emphasis was laid on knowledge discovery process using mining techniques in effort estimation techniques. Applying mining approach can incorporate further predictive feature in software modeling. Dejaeger et al. [43] have carried out a discussion where the importance of mining approaches have been made. A statistical approach is applied for performing comparative analysis on various techniques. Grbac et al. [44] have carried out a study towards effort estimation during inspection. The special consideration is about the early stage of the development process. The outcome of the study suggests that an effective decision factor significantly assists in enhancing the product reliability. Another bigger challenge in the area of software engineering the dispersion of the falsified information that leads to declination of the product quality as well as error-prone effort estimates. Study towards such problem was discussed by Jorgensen and Grimstad [45] where the authors have performed an experiment considering various organizational data. The prime purpose of the presented study is to perform cost computation of the effort being used for estimating unnecessary task. This technique plays much important role for any organization to find original effort towards productivity and not towards unnecessary trials of work. The authors have used quantitative-based methodology using statistics in order to carry out the objectives. A significant problem with effort estimation is less involvement of more number of effective quality parameters. Study towards this problem was addressed by Azath and Wahidabanu [46] using standard COCOMO model along with usage of ISO 9126 standards and its compliant quality factors. The authors have also used functional points and its outcome is assessed using total degree of influence, usability, reliability, maintainability, and efficiency. Similarly, the factors involved in effort estimation will need a precise combination of different approach to make a suitable balance between simplicity and sophistication. Therefore, study emphasizing on contents and parameters required for effort estimation was carried out by Kocaguneli et al. [47]. The author uses spatial-based approach between the instances and features that further assists in effort estimation. A CART-based approach as well as COCOMO is also utilized for active learning in order to perform predictive modeling. The same authors [48] have also performed investigation towards 10 different datasets using analogy-based approach for effort estimation.
Kocaguneli et al. [49] have also discussed that it is not necessary to select the best estimation method out of many method but to use the methods intermittently. The author concludes that selection of one method should be discouraged and inspite a combination of different method can best suit the purpose of effort estimation.

Fault Estimation Techniques
When the software is designed with certain error prone planning, it is ought to possess certain level of fault or defect. For this reason, the testing and quality assurance members are responsible for identifying a bug and remove it. However, the concept of cost computation evolves in estimating faults residing in software design. Although, majority of the existing mechanism of fault detection only works after the fault is really incorporated within the software, by that time, it becomes too late to debug it. Sometime is even a very high expensive matter to remove the faults. Hence, the concept of predictive principle in cost estimation is equally helpful for fault detection which is definitely in the early stage. The advantage is to identify the possible faults even before it could possibly inflict some serious problems in the software design. Study addressing such problem can be found in the work carried out by Fagundes et al. [50] where a predictive principle is introduced by the author. The technique jointly uses both parametric as well as non-parametric frameworks for enhancing the accuracy of fault prediction. Considering the NASA dataset, the authors have carried out experiments using machine learning language. The study outcome was found to have better capability of identifying the non-faulty to faulty methods. Ucan et al. [51] introduced an estimation processes to find the cost of "detecting defect" in the instrumented programs which may work traditionally or could be supported with a collaborative platform. It is found that the collaborative associate platform given defect of 3.76 per hour as compare to the traditional process, where it is 4.07. This work may influence the thought of web based enterprise application to consider the parameters that system having collaborative approach of development or not by introducing some factor say α ( where, the value of α will be higher if no collaborative tool used for development). The parameter α reduced the cost of development. The adoption of collaborative platform is coming mandatory as the software production process uses various models of out-sourcing, insourcing, off-shore development etc, where people are located at different geographical region and not possible to have front to front ad-hoc discussions. Sometimes hardware as well as software-based design and their associated components could be responsible for software failures. Study in such direction was carried out by Ozcelik and Yilmaz [52] where a predictive system is design that can estimate the amount of faults in the software. The evaluation of the study was carried out using a standard transformation tool in presence of multiple defects while study outcomes are evaluated using performance parameters of prediction accuracy. Predictive study towards fault computation was also carried out by Liu et al. [53] where the emphasis is mainly laid over the classification process. The technique makes use of both feature as well as reduction of number of instances as a part of data preprocessing. An analysis of relevance is carried out during the selection process of feature. It than performs controlling of redundancies using threshold-based clustering approach. Similar line of work was also carried out by Dejaeger et al. [54] by introducing a Bayesian network classifier. The authors have also investigated the feasibility of implementing Markov blanket principle with respect to Bayesian network theory. Similar NASA dataset has been used for determining line of code metrics, Halstead metrics, and McCabe metric. Monden et al. [55] have presented a technique for predicting fault as well as assessing the cost estimates out of it. With an aid of software testing, the proposed system evaluates the possible allocation techniques for effort estimation depending on the outcome of the faults. Arcuri et al. [56] have presented a technique that uses random testing in order to detect the fault in the software design. The reason behind adaption of random testing is its supportability of large number of features. Bishnu and Bhattacherjee [57] have introduced a classification technique for performing fault prediction. The authors have used K-means clustering algorithm in order to evaluate the cluster quality and predicting the possible faults in the code. Jin et al. [58] have presented a technique using support vector machine as well as neural network for assisting in selection of parameters that would positive affect the fault prediction. Database from NASA is used with multiple metrics in order to perform cross-validation followed by accuracy testing. The study outcome was found to possess a potential link between fault factors and software metrics. Software testing has also significantly gained higher degree of attention among the researchers. In accurate testing strategies will essentially lead to generation of faults and thereby it negatively affects the economy of an organization. Study towards strengthening the software testing was also carried out Ramos et al. [59]. The authors have introduced a model that significantly assists in ensuring lesser amount of defects as well as faults in the software design. It also assists in overcoming the skill gap among the testers. This competence model can be used by any organization.

OPEN RESEARCH ISSUES
From the prior section, it was seen that there are various techniques towards ensuring that cost estimation in the software design. It has been explored that the existing techniques of software cost estimation have highly diversified strategies to implement but unfortunately, it is found with higher number of challenges. All the techniques have their own advantages as well as limitations too. However, there are certain set of problems that has been found not to be addressed by the existing research work.  Less focus on Input: Basically 99% of all the existing research papers have adopted dataset e.g. NASA, where the existing frameworks considers input to be i) functional point, ii) line of source code, iii) instruction set, etc. Such technique doesn't offer an accurate outcome when it is applied for estimating cost for the software development. Such scenarios are highly static and uniform and thereby its outcome cannot be said to be applicable for dynamic environment. Hence, there was a lesser emphasis towards ensuring more precise inputs while estimating cost.  No Studies towards Computational Efficiency: Existing techniques have mainly introduced cost computation method on different dataset. There are also studies where large numbers of datasets are used with more inclusion of recursive function. Such types of approaches significantly increases both time and space complexity. Some of the studies have been claimed to offer reduced processing burden, but exact validation of it is missing in the literature. Without ensuring cost effective computation, the applicability of such cost computation techniques over low-powered devices are questionable.  More Generalized and Less Specific: The existing techniques have not taken case studies of applicability of cost estimation model on particular software. All the current investigations use the term software as a very generic model with no discrete elaboration of the system. Because of this reason, it is not sure whether the existing cost-computing models are really applicable in real-world application. At present, there are more than lakhs of software with thousand numbers of technologies running over it. It is well known that in present time's usage of wireless-based products are in increasing trends. Unfortunately, there is no such study on cost computation model that deals with wireless-based products.  No Network Consideration: Majority of the existing system uses the term software and doesn't consider anything else. In reality, it is known that maximum software is now connected with the advent of pervasive and ubiquitous computing. Hence, ignoring the network statistics and proceeding towards cost computational model for software will be impartial work. It is necessary that all the connected components of the software e.g. user, network, etc. should be considered while working over the cost computation model. techniques are more focus on cost estimation using different dataset and less towards cost minimization. Study towards an effective optimization technique will always results in minimal cost involvement. This theoretical viewpoint was not seen in many studies towards software modeling and cost estimation techniques in present times.  Few Standard Modeling towards Cost Estimation: A closer look into the outcomes of any of the recent studies towards cost estimation will show very few benchmarked techniques. Usage of COCOMO model is definitely not without flaws e.g. more prone to adopt backdated waterfall model, more experimental and less calibrated, non-supportability of duration calculation in small scale software projects. Hence, even after knowing such pitfalls, majority of the work has been using COCOMO irrespective of taking a chance to introduce a new mathematical modeling or algorithmic approach.

CONCLUSION
This paper has discussed the research traits of the software cost estimation. There are various conventional models for performing cost estimation explored in recent time e.g. algorithmic and nonalgorithmic approach. Although both the approaches has associated advantages as well as limitation, but still they are in practice at large. We also discuss the existing research trends to find that there are very less number of good research work being carried out towards software cost estimation, effort estimation, fault prediction, etc. We find that COCOMO is the backbone of majority of the existing research techniques. Our findings are i) there are very less benchmarked research methodology that can be recommended in present day, ii) not a single cost-estimation technique can be referred as a robust one, however, a combination of multiple techniques (hybridizing) can show better result, iii) none of the existing techniques are really found to address computational complexity problems, iv) there are various open research issues pertaining to existing literatures of cost-estimation approach, which will require serious consideration, etc. Hence, our future direction of the research work will be towards bridging the gap of existing system.
We have noticed that almost all the existing research work has use the term software in generic sense whereas in really there are diverse forms of it with manifold complexities. Hence, we will like to adopt a specific case study of software and make it more discrete. It is because it is not sure if any of the existing technique can be applicable in any specific software application. Hence, our first future work will be to consider a software that assists in wireless communication and the compute a cost pertaining to development of it. Our second level of future work will be to re-think on the term software and make it more applicable to the present time application and present a cost-estimation model for it. We will like to investigate about the usage of high frequency signal and their utilization over the software for civic benefits in order to see the cost involvement in it. Our final level of future work will be to ensure that our cost involvement could be possibly minimized while retaining higher product efficiency. In short, our future direction of the work will be to give a practical shape to software using a case study of it so that it becomes easy for the research community to understand the applicability of my framework.